题解 | #树的子结构#

树的子结构

http://www.nowcoder.com/practice/6e196c44c7004d15b1610b9afca8bd88

树的子结构

递归解决

    public class Solution {
        public boolean HasSubtree(TreeNode root1,TreeNode root2) {
            //这个主要是用来定位大树中节点位置的,便于与子树的头节点对应
            return (root1 != null && root2 != null) && (recursive(root1,root2) || HasSubtree(root1.left,root2) ||HasSubtree(root1.right , root2));
        }
        //树结构比较
        public boolean recursive(TreeNode nodeA, TreeNode nodeB) {
            //为什么先检查子树是否为空?子树一旦为空,就已经达到了子树的结尾部分,说明在大树中已经找到了完整的该子树
            if (nodeB == null) return true;
            //1、节点nodeA为空时,说明大树中的这个位置点缺失为空,但子树中这个位置却是有的,坑定不能继续往下走了,所以返回
            //2、当前节点位置大树和子树的节点值不一样,同样是错误的,需要返回
            if (nodeA == null || nodeA.val != nodeB.val) return false;
            //最后如果当前位置大树和子树的值和结构没问题,继续往下面的节点走,继续检查,直到检查完成
            return recursive(nodeA.left, nodeB.left) && recursive(nodeA.right, nodeB.right);
        }
    }
全部评论

相关推荐

沉淀一会:1.同学你面试评价不错,概率很大,请耐心等待; 2.你的排名比较靠前,不要担心,耐心等待; 3.问题不大,正在审批,不要着急签其他公司,等等我们! 4.预计9月中下旬,安心过节; 5.下周会有结果,请耐心等待下; 6.可能国庆节前后,一有结果我马上通知你; 7.预计10月中旬,再坚持一下; 8.正在走流程,就这两天了; 9.同学,结果我也不知道,你如果查到了也告诉我一声; 10.同学你出线不明朗,建议签其他公司保底! 11.同学你找了哪些公司,我也在找工作。
点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务