# **Leetcode筆記(Subtree of Another Tree)**

:::info
:information_source: 題目 : Subtree of Another Tree, 類型 : binary tree , 等級 : easy
日期 : 2023/03/19，2023/05/25，2023/07/05，2025/03/05
:::

### 嘗試

class Solution:
    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        if not root or not subRoot:
            return False
        
        node = self.findStart(root, subRoot)
        self.sameTree(node, subRoot)
        
    def sameTree(self, a, b):
        if not a and not b:
            return True
        if not a or b: # 大樹null
            return False
        if a or not b: # 小樹null
            return True
        if a.val != b.val:
            return False
        return (self.sameTree(a.left, a.right)) and (self.sameTree(b.left, b.right))


    def findStart(self, root, subRoot):
        if root.val == subRoot.val:
            return root
        else:
            self.findStart(root.left, subRoot)
            self.findStart(root.right, subRoot)

2023/05/25

class Solution:
    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        
        if not subRoot:
            return True
        if not root:
            return False

        def sameTree(node1, node2):
            if not node1 and not node2:
                return True
            if not node1 or not node2:
                return False
            if node1.val != node2.val:
                return False
            return (sameTree(node1.left, node2.left) and sameTree(node1.right, node2.right))

        def bfs(root, subRoot):
            # 已經窮盡到底部
            if not root:
                return False
            if sameTree(root, subRoot):
                return True
            # 記得subRoot不用變  
            # 記得這邊要回傳合格訊息 任一True即可
            return (bfs(root.right, subRoot) or bfs(root.left, subRoot))
        
        return bfs(root, subRoot)

2023/07/05
在主函式中，會先檢查root是不是和subRoot相同的，如果不是的話就往下呼叫主函式isSubtree(root.left, subRoot)和self.isSubtree(root.right, subRoot)，這個函式就會慢慢把全部的都遍歷完，有其中一次遞迴回傳True的話，因為是or判斷式，所以都會回傳True

class Solution:
    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        if not root:
            return False
        if not subRoot:
            return True

        if self.isSameTree(root, subRoot):
            return True
        else:
            l = self.isSubtree(root.left, subRoot)
            r = self.isSubtree(root.right, subRoot)
            return l or r # 只要有一層回傳True
            # 那總會往上傳到整個都是True


    def isSameTree(self, q, p):
        if not q and not p:
            return True
        if not q or not p:
            return False
        if q.val != p.val:
            return False
        
        return (self.isSameTree(q.left, p.left) and self.isSameTree(q.right, p.right))

2025/03/05
主函式檢查是否為相同樹，如果不是，則遞迴檢查其左右樹，以左樹或右樹為root。isSubtree的self.sameTree呼叫，可以想像是base case，只要有一為True，則回傳True

class Solution:
    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        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, node1, node2):
        if not node1 and not node2:
            return True
        elif not node1 or not node2:
            return False
        elif node1.val != node2.val:
            return False
        
        return self.sameTree(node1.left, node2.left) and self.sameTree(node1.right, node2.right)

---
### **優化**

原本不太懂為什麼還要呼叫一次isSubtree，最後得出可能跟root是誰有關，如果不重新呼叫的話，root永遠是從最上面開始
時間複雜度O(s*t)，時間複雜度是考慮最差的情況發生，即每個s和t都要跑一整遍

class Solution:
    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        if not root: # 大樹null
            return False
        if not subRoot: # 小樹null
            return True
        
        if self.sameTree(root, subRoot):
            # 若讓sametree一直跑 結果為true
            # self.sameTree(root, subRoot)回傳bool
            return True
        else:
            # 更換root
            return ( self.isSubtree(root.right, subRoot) or self.isSubtree(root.left, subRoot) )
        
    def sameTree(self, a, b):
        if not a and not b: # 最後都是null
            return True
        if not a or not b:
            return False
        if a.val != b.val:
            return False
        # 跑到這 val相同且ab皆不為null

        return (self.sameTree(a.left, b.left) and self.sameTree(a.right, b.right))

比較像自己原本的寫法的優化

class Solution:
    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        
        if self.subtree(root, subRoot):
            return True
        else:
            return False
        
    def sameTree(self, a, b):
        if not a and not b: # 最後都是null
            return True
        if not a or not b:
            return False
        if a.val != b.val:
            return False
        # 跑到這 val相同且ab皆不為null

        return (self.sameTree(a.left, b.left) and self.sameTree(a.right, b.right))
    
    def subtree(self, root, subRoot):
        if not root: # 大樹null
            return False
        if not subRoot: # 小樹null
            return True

        if self.sameTree(root, subRoot):
            # 若讓sametree一直跑 結果為true
            # self.sameTree(root, subRoot)回傳bool
            return True
        else:
            # 更換root
            return ( self.subtree(root.right, subRoot) or self.subtree(root.left, subRoot) )

---

**:warning: 錯誤語法**
:::warning
如果要創一個function，位置是和原function平行，並且要記得加self，def sameTree(self, a, b)
呼叫自己的時候也要記得加self
若在return東西的時候，若順便呼叫自己，要把東西用括號括起來，可以想成return只能傳一個bool
:::

**:thumbsup:學習**
:::success
subtree : 包含全部該點下面的node
:::

**思路**

**講解連結**
https://www.youtube.com/watch?v=E36O5SWp-LE
https://www.youtube.com/watch?v=wDsFfgv4OGY

Provided by. NeetCode & nETSETOS(很好的講解遞迴)

###### tags: `binary tree` `medium` `leetcode`