Description
Check if one tree is a subtree of another.
Constraints
- Time Complexity:
O(m·n) - Space Complexity:
O(m)
Tags
treedfsstring-matchinghash-function
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