[LeetCode]572. A subtree of another tree

subject

572.  The subtree of another tree 
 Here are two binary trees  root  and  subRoot . test  root  Whether and  subRoot  Subtrees with the same structure and node values . If there is , return  true ; otherwise , return  false .

 Binary tree  tree  A subtree of includes  tree  A node of and all descendants of this node .tree  It can also be seen as a subtree of its own .

 

 Example  1：


 Input ：root = [3,4,5,1,2], subRoot = [4,1,2]
 Output ：true
 Example  2：


 Input ：root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
 Output ：false
 

 Tips ：

root  The number of nodes on the tree ranges from  [1, 2000]
subRoot  The number of nodes on the tree ranges from  [1, 1000]
-104 <= root.val <= 104
-104 <= subRoot.val <= 104

Method 1：dfs

public boolean isSubtree(TreeNode root, TreeNode subRoot) {
    
    if (root == null || subRoot == null) {
    
        return root == null && subRoot == null;
    }
    // Be careful , If the comparison is root, Compare the same tree :isSameTree
    // If the comparison is root Left and right child nodes , Then compare whether it is a subtree  ：isSubtree
    return isSameTree(root, subRoot) ||
            isSubtree(root.left, subRoot) ||
            isSubtree(root.right, subRoot);

}

private boolean isSameTree(TreeNode source, TreeNode target) {
    
    if (source == null || target == null) {
    
        return source == null && target == null;
    }
    return source.val == target.val &&
            isSameTree(source.left, target.left) &&
            isSameTree(source.right, target.right);
}