572. 另一棵树的子树

给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。
二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。

示例 1：
输入：root = [3,4,5,1,2], subRoot = [4,1,2]

      3      
    /   \    
  4       5  
 / \         
1   2     
   4   
  / \  
 1   2

输出：true

示例 2：
输入：root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]

            3            
         /     \         
      4           5      
    /   \                
  1       2              
         /               
        0     
   4   
  / \  
 1   2

输出：false
�
结合深度优先递归遍历的算法框架：
当 root 节点的值和 subRoot 节点的值开始相等的时候可以开始判断

boolean isSubtree = false;
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
    order(root, subRoot);
    return isSubtree;
}
public void order(TreeNode root, TreeNode subRoot) {
    if (root == null) {
        return;
    }
    if (root.val == subRoot.val) {
        isSubtree = ?
    } else {
        order(root.left, subRoot);
        order(root.right, subRoot);
    }
}

当 root 节点的值和 subRoot 节点的值相等时此时可以看成判断两棵树是否相同，可以参考 LeetCode 100. 相同的树：

public boolean isSameTree(TreeNode p, TreeNode q) {
    if (p == null && q == null) {
        return true;
    }
    if (p != null && q != null && p.val == q.val) {
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
    return false;
}

完整算法：

boolean isSubtree = false;
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
    order(root, subRoot);
    return isSubtree;
}
private void order(TreeNode root, TreeNode subRoot) {
    if (root == null) {
        return;
    }
    if (root.val == subRoot.val) {
        isSubtree = isSameTree(root, subRoot);
    } else {
        order(root.left, subRoot);
        order(root.right, subRoot);
    }
}
private boolean isSameTree(TreeNode p, TreeNode q) {
    if (p == null && q == null) {
        return true;
    }
    if (p != null && q != null && p.val == q.val) {
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
    return false;
}

提交后，测试用例未通过：
输入：root = [1,1], subRoot = [1]
测试结果：false
期望结果：true

说明思路有问题，只判断一次 root.val == subRoot.val 是不够的，应当需要不断的遍历 root 树，不断比较 root 的子树是否和 subRoot 树一致：

public boolean isSubtree(TreeNode root, TreeNode subRoot) {
    boolean rootIsSame = isSameTree(root,subRoot);
    boolean leftIsSame = isSubtree(root.left, subRoot);
    boolean rightIsSame = isSubtree(root.right, subRoot);
    return rootIsSame || leftIsSame || rightIsSame;
}
private boolean isSameTree(TreeNode p, TreeNode q) {
    if (p == null && q == null) {
        return true;
    }
    if (p != null && q != null && p.val == q.val) {
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
    return false;
}

补全参数有效性检查

public boolean isSubtree(TreeNode root, TreeNode subRoot) {
    if (subRoot == null) {
        // subRoot 为 null 一定都是 true
        return true;
    }
    if (root == null) {
        // subRoot 一定不为 null, 只要 root 为 null，肯定是 false
        return false;
    }
    boolean rootIsSame = isSameTree(root,subRoot);
    boolean leftIsSame = isSubtree(root.left, subRoot);
    boolean rightIsSame = isSubtree(root.right, subRoot);
    return rootIsSame || leftIsSame || rightIsSame;
}
private boolean isSameTree(TreeNode p, TreeNode q) {
    if (p == null && q == null) {
        return true;
    }
    if (p != null && q != null && p.val == q.val) {
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
    return false;
}