【Leetcode 筆記】572. Subtree of Another Tree

題目解釋

給定兩個 binary tree root 和 subRoot 的根，
如果 root 的子樹具有相同的結構和 subRoot 的節點值，則傳回 true，
否則傳回 false。

子樹定義：

1. Binary tree 的子樹是由樹中的一個節點和該節點的所有後代 (descendants) 組成的樹。
2. 樹也可以被視為其自身的子樹。

範例

• 輸入: root = [3, 4, 5, 1, 2], subRoot = [4, 1, 2]
• 輸出: True

subRoot 是 root 的子樹。

最佳解法

Traverse 整棵 root，然後使用 _isSameTree 判定兩樹是否相同。

關於 _isSameTree 的實作請回頭看：【Leetcode 筆記】100. Same Tree

注意，最後 return 的條件式是用 or，
因為 root 的左子樹或右子樹只要跟 subtree 相同就算是 ok。

程式碼

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

            if (p and not q) or (not p and q) or (p.val != q.val):
                return False
            else:
                return _isSameTree(p.left, q.left) and _isSameTree(p.right, q.right)

        if not root:
            return False

        if _isSameTree(root, subRoot):
            return True

        return self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)

時間複雜度

O(n * m)，因為對於 root 中的每個節點，都可能呼叫 _isSameTree 檢查是否與 subRoot 相符。

空間複雜度

O(h)，h 是 root 的高度，長的平均的話最好情況是 O(log n)。

結語

雙重遞迴，就看玩的 6 不 6… 。

• About
• Latest Posts

數據女巫 𝔻.𝕡𝕪𝕤 🔮

𝐀𝐈 𝐀𝐫𝐭𝐢𝐬𝐭 • 𝐒𝐨𝐟𝐭𝐰𝐚𝐫𝐞 𝐄𝐧𝐠𝐢𝐧𝐞𝐞𝐫
﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊
致力於打破現有框架的 AI 藝術創作者，曾接受藝文雜誌的個人專訪，作品於香港實體展出。有擔任大學講座講師與 Stable Diffusion AI 年會講者的經驗。擅長 Live Prompting，曾獲 GIGABYTE VS AI 街頭對戰冠軍、ASUS 校園 AI 繪圖競賽亞軍等殊榮。
---
歡迎合作邀約 / 委託 / 各式交流
ᴇᴍᴀɪʟ：dpys@techmagichouse.art

Latest posts by 數據女巫 𝔻.𝕡𝕪𝕤 🔮 (see all)

• [推薦工具] 讓程式碼截圖變的美美的吧！VScode CodeSnap 與 3 種同功能線上工具介紹 - 2025-01-05
• [AI 繪圖初級教學] 用 X/Y/Z Plot 比較 Stable Diffusion 的 prompt 與 LoRA 效果 - 2024-12-27
• [AI 繪圖中級篇教學] Stable Diffusion WebUI WD14 Tagger 介紹 - 2024-12-26