【Leetcode 筆記】226. Invert Binary Tree

題目解釋

給定 binary tree 的 root，反轉 tree 並 return 其 root。

範例

• 輸入: root = [4, 2, 7, 1, 3, 6, 9]
• 輸出: [4, 7, 2, 9, 6, 3, 1]

left child 跟 right child 都被交換了。

最佳解法

在寫 Tree 的題目時，最重要的就是 遞迴 (Recursion) 的概念。

我們可以把這題拆解為

1. 處理目前節點（交換其左右子樹）
2. 遞迴的處理左子樹
3. 遞迴的處理右子樹

說明

我們一層一層的向下傳播要反轉的邏輯 (以這題而言是反轉)，
直到 root 沒有東西才一層層的又往上 return。

我們會不斷的先往左邊走，都 return 回根節點後再來才是向右走，
所以這是一種 深度優先探索 (DFS) 的演算法。

程式碼

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root:
            return
        else:
            root.left, root.right = root.right, root.left

            self.invertTree(root.left)
            self.invertTree(root.right)

        return root

時間複雜度

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

空間複雜度

如果樹是 skewed 的話，最差情況是 O(n)，
但如果是長的平均的 tree 就是 O(log n)。

結語

Tree 的 pattern 要熟記 (對自己喊話)

• 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