剑指offer-17-树的子结构

思路：

• 递归

踩坑

本题测试用例较少，只要比较root1及其左右子树 就能ac

代码

能AC但是错误的代码

public class Solution {
    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
        if(root1==null || root2==null){
            return false;}
        //这里只比较了root，root.left,root.right
        return JudgeNode(root1,root2)||JudgeNode(root1.left,root2)||JudgeNode(root1.right,root2);         
        }
    public boolean JudgeNode(TreeNode Node1,TreeNode Node2){
        if(Node2==null){return true;}
        if(Node1==null){return false;} //包含了隐含条件 Node2!=null

        if(Node1.val==Node2.val){
            return JudgeNode(Node1.left,Node2.left) && JudgeNode(Node1.right,Node2.right);
            }else{return false;}
    }
}

正确的代码

public class Solution {
    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
        if(root2==null ||root1==null){return false;}
        if(root1.val==root2.val && judge(root1,root2)){
             return true;
        }else { //递归调用 判断子树是否与root相等
            return HasSubtree(root1.left,root2)||HasSubtree(root1.right,root2);
        }
    }

    public boolean judge(TreeNode root1,TreeNode root2){
        if(root2==null){return true;}
        if(root1==null){return false;}
        if(root1.val==root2.val){ 
                return judge(root1.left,root2.left) && judge(root1.right,root2.right);
        }else{
                return false;
             }
        }

}