# Leetcode 572. Subtree of Anthor Tree

## 題解

<iframe width="560" height="315" src="https://www.youtube.com/embed/E36O5SWp-LE?si=oUbYesoFuIcUbiey" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share" allowfullscreen></iframe>
<br></br>

# 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:
    # Time complexity: O(m+n)
    # Space complexity: O(n)
    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        # But if the subRoot is None, what matter the root it is, the subRoot always is the root's subTree
        if not subRoot: return True
        # If root is None meats what matter the subRoot it is ,the subRoot always not gonna be root's sub tree
        if not root: return False

        if self.sameTree(root,subRoot):
            return True
        
        return (self.isSubtree(root.left,subRoot) or
        self.isSubtree(root.right,subRoot))
    
    def sameTree(self, s: TreeNode, t: TreeNode):
        if not s and not t:
            return True
        
        if s and t and s.val == t.val:
            return (self.sameTree(s.left,t.left) and self.sameTree(s.right,t.right))
        
        return False