LC 0572 [E] Subtree of Another Tree - ALawliet/algorithms GitHub Wiki

# 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)