“子问题的递归处理”——判断两棵树是不是相同的树——以及 另一颗树的子树

“子问题的递归处理”——先看根节点，再看左右子树

1. 检查两颗树是否相同

做题逻辑

1. 就以根节点 为基础
   先判断 两个树的根节点 进行对比
2. 如果两个根节点 没问题
   那么就看 这个根节点的 左右子树 和另一个根节点的左右子树是不是有问题
   

原题链接

return false的情况

1. 一空一不空 || 两个值不同

return true

1. 两个都为空

递归在于 return 递归函数

public boolean isSameTree(TreeNode p, TreeNode q) {
    
    //这里只是判断的 一个为空 一个不为空的情况 。
    // 你没有判断 两个都是空 和 两个都不是空的情况
    if(p == null && q != null || p != null && q == null) {
    
        return false;
    }

    if(p == null && q == null) {
    
        return true;
    }

    if(p.val != q.val) {
    
        return false;
    }

    //p != null && q != null && p.val == q.val
    return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
}

2. 另一颗树的子树（时间复杂度：O(n*m)）

原题链接

    public boolean isSameTree(TreeNode p, TreeNode q) {
    
        //这里只是判断的 一个为空 一个不为空的情况 。
        // 你没有判断 两个都是空 和 两个都不是空的情况
        if(p == null && q != null || p != null && q == null) {
    
            return false;
        }

        if(p == null && q == null) {
    
            return true;
        }

        if(p.val != q.val) {
    
            return false;
        }

        //p != null && q != null && p.val == q.val
        return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
    }
    //时间复杂度：O(n*m) 假设root这棵树的节点个数n subRoot节点个数是m
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
    
        if(root == null) return false;

        if(isSameTree(root,subRoot)) return true;

        if(isSubtree(root.left,subRoot)) return true;

        if(isSubtree(root.right,subRoot)) return true;

        return false;
    }

逻辑：1. 如果树为空 不可能有子树 return flase

if(root == null) return false;

2. 如果 根 与 子树 正好相等 return true

if(isSameTree(root,subRoot)) return true;

3. 如果 根的左 与 子树正好相等 return true

if(isSubtree(root.left,subRoot)) return true;

4. 如果 根的右 与 子树正好相等 return true

if(isSubtree(root.right,subRoot)) return true;

5. if 都没有满足 那么 return false

注意：其实代码在 递归过程中，不仅仅是比较了 根的左和右，（如果没有想要的）还比较的其余的根的左右

原因：代码在递归的过程中，走遍了每个根节点