Description
Determine whether a nonempty candidate tree exactly matches a subtree rooted at some node of the main tree.
Solution
import sys
sys.setrecursionlimit(100_000)
def is_subtree(root, subRoot):
def same(a, b):
if not a or not b:
return a is b
return a.val == b.val and same(a.left, b.left) and same(a.right, b.right)
if not root:
return False
return same(root, subRoot) or is_subtree(root.left, subRoot) or is_subtree(root.right, subRoot)Examples
Inputs are positional arguments. Trees use level-order arrays; linked lists use value arrays. Design problems list operations in order.
Example 1
- Input
[[3,1,4],[1]]- Output
true
The leaf containing 1 exactly matches the candidate.
Example 2
- Input
[[3,1,4],[1,2]]- Output
false
The candidate requires a child missing from the main tree.
Example 3
- Input
[[1],[1]]- Output
true
A tree is a subtree of itself.
Approach
At every node, test full structural equality or search either child.
Time & space
O(n m) time; O(h + g) recursion space for tree sizes n,m and heights h,g.