Subtree of Another Tree
EasyTrees
Given the roots of two binary trees, root and subRoot, return True if root contains a subtree that is identical to subRoot, and False otherwise.
A subtree of root is a node of root together with all of its descendants. Identical means the same shape with the same values in matching positions. root itself counts as one of its subtrees.
Trees are written in level order: values are listed level by level, left to right, and null marks a missing child (trailing nulls are omitted).
Example 1
- Input:
- root = [5,3,8,1,4,null,9], subRoot = [3,1,4]
- Output:
- True
- Explanation
- The node 3 in
roothas children 1 and 4 and nothing below them, which is exactlysubRoot.
Example 2
- Input:
- root = [1,1,1,null,2], subRoot = [1,2]
- Output:
- False
- Explanation
subRoothangs its 2 on the left, but the only 2 inroothangs on the right, so no subtree matches. The match has to cover a whole subtree, including its shape.
Example 3
- Input:
- root = [5,3,8,1,4,null,9,null,null,2], subRoot = [3,1,4]
- Output:
- False
- Explanation
- The top of the subtree at 3 looks like
subRoot, but 4 has an extra child 2. A subtree includes all descendants, so this is not a match.
Constraints
- The number of nodes in
rootis in the range[1, 2000] - The number of nodes in
subRootis in the range[1, 1000] -10^4 <= Node.val <= 10^4