Subtree of Another Tree
Given the roots of two binary trees root and subRoot, return true if there is a subtree of root with the same structure and node values of subRoot, and false otherwise.
A subtree of a binary tree tree is a tree that consists of a node in tree and all of this node's descendants. The tree tree could also be considered as a subtree of itself.
Example 1
3 4
/ \ / \
4 5 1 2
/ \
1 2Input
root = [3,4,5,1,2], subRoot = [4,1,2]Output
trueThe tree rooted at node 4 in
root has the same structure and node values as subRoot.Example 2
3 4
/ \ / \
4 5 1 2
/ \
1 2
/
0Input
root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]Output
falseAlthough
root contains a node with value 4 and children 1 and 2, that subtree has an additional descendant 0, so it does not match subRoot.Constraints
- The number of nodes in the
roottree is in the range[1, 2000]. - The number of nodes in the
subRoottree is in the range[1, 1000]. - -10^4 <= root.val <= 10^4
- -10^4 <= subRoot.val <= 10^4