572 - Subtree of Another Tree
Written on January 16, 2020
Tweet
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.
class Solution:
def isSubtree(self, s: TreeNode, t: TreeNode) -> bool:
if not t:
return True
elif not s:
return False
return self.isSametree(s, t) or self.isSubtree(s.left, t) or self.isSubtree(s.right, t)
def isSametree(self, s1, s2):
if not s1 or not s2:
return s1 == s2
return s1.val == s2.val and self.isSametree(s1.left, s2.left) and self.isSametree(s1.right, s2.right)