# 572. Subtree of Another Tree
Given two non-empty binary trees s and t, check whether tree t has exactly the same structure and node values with a subtree of s. A subtree of s is a tree consists of a node in s and all of this node's descendants. The tree s could also be considered as a subtree of itself.
Example1:
Given tree s:
3
/ \
4 5
/ \
1 2
Given tree t:
4
/ \
1 2
Return true, because t has the same structure and node values with a subtree of s.
Example2:
Given tree s:
3
/ \
4 5
/ \
1 2
/
0
Given tree t:
4
/ \
1 2
Return false.
# Solution
Approach 1: recursive -- look for t within s by comparing nodes. Time: up to O(m*n)
where s has m nodes & t has n nodes; space: O(m)
-- the depth of recursion.
Approach 2: iterative -- same idea. Space now is O(m) + O(n)
.
# Code (Python)
Approach 1:
class Solution:
def isSubtree(self, s, t):
"""
:type s: TreeNode
:type t: TreeNode
:rtype: bool
"""
if not s and not t:
return True
if (s and not t) or (t and not s):
return False
if s.val == t.val and self._is_same_tree(s, t):
return True
return self.isSubtree(s.left, t) or self.isSubtree(s.right, t)
def _is_same_tree(self, t1, t2):
if not t1 and not t2:
return True
if (t1 and not t2) or (t2 and not t1) or t1.val != t2.val:
return False
return (t1.val == t2.val and
self._is_same_tree(t1.left, t2.left) and
self._is_same_tree(t1.right, t2.right))
Approach 2:
def isSubtree(self, s, t):
# iterative: also look for t within s by comparing nodes
if not s:
return not t
node = s
stack = []
while node:
stack.append(node)
node = node.left
while stack:
node = stack.pop()
if node.val == t.val and self._is_same_tree_iterative(node, t):
return True
node = node.right
while node:
stack.append(node)
node = node.left
return False
def _is_same_tree_iterative(self, t1, t2):
stack1, stack2 = [t1], [t2]
while stack1 and stack2:
n1, n2 = stack1.pop(), stack2.pop()
if n1.val != n2.val:
return False
if n1.right and n2.right:
stack1.append(n1.right)
stack2.append(n2.right)
elif (n1.right and not n2.right) or (n2.right and not n1.right):
return False
if n1.left and n2.left:
stack1.append(n1.left)
stack2.append(n2.left)
elif (n1.left and not n2.left) or (n2.left and not n1.left):
return False
return not stack1 and not stack2
# Code (C++)
Approach 1:
Approach 2: