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.
Example 1:
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.
Example 2:
Given tree s:
3
/ \
4 5
/ \
1 2
/
0
Given tree t:
4 / \ 1 2
Return false.
Source
def is_subtree(self, s, t):
"""Simple recursive approach.
Time Complexity: O(|s| * |t|)
Space Complexity: O(|s|)
"""
def is_match(s, t):
if s is None or t is None:
return s == t
if s.val == t.val:
return is_match(s.left, t.left) and is_match(s.right, t.right)
return False
if t is None: # not really needed
return True # not really needed
if s is None:
return False
if is_match(s, t):
return True
# if not, keep inspecting the rest of the tree
return is_subtree(s.left, t) or is_subtree(s.right, t)
def is_subtree(self, s, t):
"""using string conversion
Time Complexity O(|s|+|t|) on average O(|s|*|t|) worst case
Space Complexity: O(|s|+|t|)
"""
def convert(p):
if not p: # base case
return "." # add suffix
return "#" + str(p.val) + convert(p.left) + convert(p.right) # add prefix, see below
return convert(t) in convert(s) # python implemention of 't in s' is based on Boyer-More
# O(|s|) on average, O(|s|*|t|) worst case
# SUFFIX '.'' IS NEEDED FOR FOLLOWING CASE
# t = [2,3] s = [1,2,3]
# WITHOUT #2#3 #1#2#3 ==> True (wrong answer)
# WITH #2#3... #1#2..#3.. ==> False (correct answer)
# PREFIX '#' IS NEEDED FOR FOLLOWING CASE
# t = [2] s = [12]
# WITHOUT 2.. 12.. ==> True (wrong answer)
# WITH #2.. #12.. ==> False (correct answer)
def is_subtree(self, s, t):
"""Same as above but in one line."""
def convert(p):
return "#" + str(p.val) + convert(p.left) + convert(p.right) if p else "."
return convert(t) in convert(s)