226. Invert Binary Tree

Easy

Description

給定一棵二元樹的根節點，將整棵樹左右翻轉（鏡像），回傳翻轉後的根節點。每個節點的左右子樹互換。

Example:

Input: root = [4,2,7,1,3,6,9] Output: [4,7,2,9,6,3,1]

Intuition#

對每個節點，交換其左右子節點，然後遞迴處理子樹。

翻轉一棵樹 = 交換根的左右子樹 + 分別翻轉左右子樹
這是一個天然的遞迴結構，也可以用迭代（BFS/DFS）完成

Approaches#

⭐ 1: Recursive DFS#

概念: 後序遍歷，先遞迴翻轉左右子樹，再交換左右子節點
時間複雜度: O(n)，每個節點訪問一次
空間複雜度: O(h)，遞迴堆疊深度，h 為樹高

class Solution {
    fun invertTree(root: TreeNode?): TreeNode? {
        if (root == null) return null
        val left = invertTree(root.left)
        val right = invertTree(root.right)
        root.left = right
        root.right = left
        return root
    }
}

2: Iterative BFS#

概念: 使用佇列進行層序遍歷，對每個節點交換左右子節點
時間複雜度: O(n)
空間複雜度: O(n)，佇列最多存放一層的節點

class Solution {
    fun invertTree(root: TreeNode?): TreeNode? {
        if (root == null) return null
        val queue: ArrayDeque<TreeNode> = ArrayDeque()
        queue.add(root)
        while (queue.isNotEmpty()) {
            val node = queue.removeFirst()
            val temp = node.left
            node.left = node.right
            node.right = temp
            node.left?.let { queue.add(it) }
            node.right?.let { queue.add(it) }
        }
        return root
    }
}

🔑 Takeaways#

Pattern: 樹的遞迴結構 — 問題可分解為「對當前節點操作 + 遞迴處理子樹」
關鍵技巧: 遞迴是處理樹結構最直覺的方式，幾乎所有樹的變換問題都能用這個模式