Core Insight Ask each subtree for exactly the information its parent needs, then combine the two answers.
Common Pitfall Define the base case before combining left and right subtree results.
Description
Check if one tree is a subtree of another.
Constraints
- Time Complexity:
O(m·n) - Space Complexity:
O(m)
Tags
treedfsstring-matchinghash-function
Implementation Plan Translate the invariant into these small, testable moves.
- Define what one recursive call returns.
- Handle an empty node.
- Recurse into children.
- Combine the child results at the current node.
def isSubtree(s, t):
if not t:
return True
if not s:
return False
if isSameTree(s, t):
return True
return isSubtree(s.left, t) or isSubtree(s.right, t)
def isSameTree(p, q):
if not p and not q:
return True
if p and q and p.val == q.val:
return (isSameTree(p.left, q.left) and
isSameTree(p.right, q.right))
return False