【Leetcode 筆記】100. Same Tree

題目解釋

給定兩個 binary tree p 和 q 的 root，
寫一個函數來檢查它們是否相同。

如果兩個二元樹 結構相同 且 節點具有相同的值 ，則認為它們是相同的。

範例

• 輸入: p = [1, 2, 3], q = [1, 2, 3]
• 輸出: True

p 跟 q 的結構與 node 的值皆相同。

最佳解法

如果 p 跟 q 同時 都沒有了，代表我們應該 return True 回去。

但是如果 p 先沒了或是 q 先沒了，
就代表他們不是同棵樹，所以要 return False。

當然，p 的值跟 q 的值不一樣的話也是不行的❗

程式碼

class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        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 self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

時間複雜度

O(n)，n 是 binary tree 的 node 個數。

空間複雜度

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

結語

善用 return 的值。

• 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