463. Tree Inside Tree
Two folder layouts are stored as binary trees: the big layout root and a smaller template sub. A template is said to appear in the layout when some node of root, taken together with every one of its descendants, forms a tree that is identical to sub: same shape, and equal values at every matching position.
Return true if the template appears in the layout and false otherwise. A node that has extra descendants beyond those of sub does not match, and root itself is allowed to be the matching node.
Example 1
- Input:
- root = [9,6,14,2,7,11,20,null,null,null,8]sub = [6,2,7,null,null,null,8]
- Output:
- true
- Explanation:
The subtree rooted at 6 in root has children 2 and 7 with 7 holding a right child 8, which matches sub exactly.
Example 2
- Input:
- root = [9,6,14,2,7,11,20,null,null,null,8]sub = [6,2,7]
- Output:
- false
- Explanation:
Node 7 in root has a descendant 8, but sub's 7 has none, so no subtree of root is identical to sub.
Example 3
- Input:
- root = [9,6,14,2,7,11,20,null,null,null,8]sub = [14,11,20]
- Output:
- true
- Explanation:
The subtree rooted at 14 has exactly children 11 and 20, equal to sub.
Constraints
1 ≤ number of nodes in root ≤ 1000
1 ≤ number of nodes in sub ≤ 1000
-100 ≤ Node.val ≤ 100 in both trees (values may repeat)
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n * m)
- Space
- O(h)