Does One Tree Hide Inside Another
Implement containsSubtree
You are given two binary trees, root and sub. Decide whether sub appears inside root: there must be a node in root such that the piece of root consisting of that node and all of its descendants is identical to sub, with the same shape and the same values. The empty tree is considered to appear in every tree.
Trying an exact comparison at every node works. You can avoid most comparisons by noticing that a matching piece must have exactly the same height as sub.
Example 1:
Input: root = [9,5,14,3,7,null,20], sub = [5,3,7]
Output: true
Example 2:
Input: root = [4,2,6,1], sub = [2]
Output: false
Example 3:
Input: root = [3,8], sub = []
Output: true
+ 13 hidden test cases run on Submit.
Constraints:
- ●
0 ≤ number of nodes in root ≤ 200; 0 ≤ number of nodes in sub ≤ 100 - ●
−100 ≤ node.val ≤ 100 in both trees - ●
Each tree is given by its root node (null for an empty tree) - ●
Return true when some node of root has a subtree — that node together with ALL of its descendants — that is identical to sub in shape and values. An empty sub is contained in every tree
root =
[9, 5, 14, 3, 7, null, 20]
sub =
[5, 3, 7]