攜手創作，共同成長！這是我參與「掘金日新計劃 · 8 月更文挑戰」的第18天，點選檢視活動詳情 

題目

給你一棵二叉樹的根節點 root，翻轉這棵二叉樹，並返回其根節點。

說明： xxx

示例 1：

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

示例 2：

• 輸入：root = [2,1,3]
• 輸出：[2,3,1]

示例 3：

• 輸入：root = []
• 輸出：[]

方法一：遞迴

思路及解法

這是一道很經典的二叉樹問題。顯然，我們從根節點開始，遞迴地對樹進行遍歷，並從葉子節點先開始翻轉。如果當前遍歷到的節點 $root$ 的左右兩棵子樹都已經翻轉，那麼我們只需要交換兩棵子樹的位置，即可完成以 $root$ 為根節點的整棵子樹的翻轉。

程式碼

``` class Solution { func invertTree(_ root: TreeNode?) -> TreeNode? { if nil == root { return root }

    let left: TreeNode? = invertTree(root?.left)
    let right: TreeNode? = invertTree(root?.right)
    root?.left = right
    root?.right = left
    return root
}

} ```

複雜度分析

• 時間複雜度：$O(N)$，其中 $N$ 為二叉樹節點的數目。我們會遍歷二叉樹中的每一個節點，對每個節點而言，我們在常數時間內交換其兩棵子樹。

• 空間複雜度：$O(N)$。使用的空間由遞迴棧的深度決定，它等於當前節點在二叉樹中的高度。在平均情況下，二叉樹的高度與節點個數為對數關係，即 $O(logN)$。而在最壞情況下，樹形成鏈狀，空間複雜度為 $O(N)$。

方法二：迭代

思路及解法

遞迴實現也就是深度優先遍歷的方式，那麼對應的就是廣度優先遍歷。 廣度優先遍歷需要額外的資料結構--佇列，來存放臨時遍歷到的元素。 深度優先遍歷的特點是一竿子插到底，不行了再退回來繼續；而廣度優先遍歷的特點是層層掃蕩。 所以，我們需要先將根節點放入到佇列中，然後不斷的迭代佇列中的元素。 對當前元素調換其左右子樹的位置，然後： * 判斷其左子樹是否為空，不為空就放入佇列中 * 判斷其右子樹是否為空，不為空就放入佇列中

程式碼

``` class Solution { func invertTree(_ root: TreeNode?) -> TreeNode? { if nil == root { return root }

    var queue: [TreeNode?] = []
    queue.append(root)
    while !queue.isEmpty {
        let tmp: TreeNode? = queue.removeLast()
        let left: TreeNode? = tmp?.left
        tmp?.left = tmp?.right
        tmp?.right = left

        if tmp?.left != nil {
            queue.append(tmp?.left)
        }

        if tmp?.right != nil {
            queue.append(tmp?.right)
        }
    }
    return root
}

} ```

複雜度分析

• 時間複雜度：每個節點都需要入佇列/出佇列一次，所以是 $O(n)$

• 空間複雜度：最壞的情況下會包含所有的葉子節點，完全二叉樹葉子節點是 $n/2$ 個，所以時間複雜度是 $O(n)$