LC 0572 [E] Subtree of Another Tree
Code with Senpai edited this page Feb 4, 2022
·
3 revisions
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def isSubtree(self, s, t):
# this helper function will keep going down the tree until there's a combo break before the main function goes next
def isMatch(s, t):
if not s or not t:
return s is t
else:
return s.val == t.val and isMatch(s.left, t.left) and isMatch(s.right, t.right)
if not s: # if no root, then it obviously won't have the subRoot
return False
if isMatch(s, t): # check if the current root and subTree are identical
return True
else: # otherwise go down the root with the same subTree
return self.isSubtree(s.left, t) or self.isSubtree(s.right, t)
footer