Description
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.
Examples
Input:
root = [3,4,5,1,2], subRoot = [4,1,2]Output:
trueExplanation:
The subtree rooted at node 4 matches.
Input:
root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]Output:
falseExplanation:
The subtree rooted at node 4 in the main tree has an extra child node 0, so it does not match subRoot [4,1,2].
Input:
root = [1,2,3,4,5], subRoot = [2,4,5]Output:
trueExplanation:
The left subtree rooted at node 2 has the exact same structure and values as subRoot. Node 2 has left child 4 and right child 5, which perfectly matches the subRoot tree.
Constraints
- •
Number of nodes in root is in range [1, 2000] - •
Number of nodes in subRoot is in range [1, 1000]