572. Subtree of Another Tree

attention to

if root.val == subRoot.val:
            # call isSameTree instead of isSubtree, otherwise it returns tree for below test case
            if self.isSameTree(root.left, subRoot.left) and self.isSameTree(root.right, subRoot.right):
                return True

  1
2   3

   1
 4   5
2     3

time O(N * M) where N is number of nodes in root and M is number of nodes in subRoot. space is O(hight(root1) + hight(subRoot))

class Solution:
    # check if a tree contains a subtree
    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        if not root and not subRoot:
            return True
        
        if not root or not subRoot:
            return False
        
        if root.val == subRoot.val:
            # call isSameTree instead of isSubtree
            if self.isSameTree(root.left, subRoot.left) and self.isSameTree(root.right, subRoot.right):
                return True
        
        if self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot):
            return True
        
        return False
    
    # check if 2 trees are same
    def isSameTree(self, root1, root2):
        if not root1 and not root2:
            return True
        if not root1 or not root2:
            return False
        
        if root1.val != root2.val:
            return False

        return self.isSameTree(root1.left, root2.left) and self.isSameTree(root1.right, root2.right)

an alternative solution is to first serialize tree (leetcode 297. Serialize and Deserialize Binary Tree) then check if string contains substring (in in python uses kmp algorithm and has time complexity of O(m+n))

to compare 12 vs 2 properly

we need to use res = [SEPARATOR, str(root.val), SEPARATOR] -> ',12,' vs ',2,'
in 297 we can simply use res = [str(root.val)] -> '12' vs '2' -> false positive

SEPARATOR = ','
NONE_NODE = '#'

class Solution:
    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        encoded_root = ','.join(self.encode(root))
        encoded_sub_root = ','.join(self.encode(subRoot))
        return encoded_sub_root in encoded_root

    def encode(self, root: TreeNode) -> list: 
        if not root:
            return [NONE_NODE]

        res = [SEPARATOR, str(root.val), SEPARATOR]
        res.extend(self.encode(root.left))
        res.extend(self.encode(root.right))
        return res

572. Subtree of Another Tree - cocoder39/coco39_LC GitHub Wiki