LeetCode中如何翻轉二叉樹

# LeetCode中如何翻轉二叉樹

## 引言

翻轉二叉樹（Invert Binary Tree）是LeetCode上一道經典的二叉樹問題（題目編號226）。它不僅考察了對二叉樹結構的理解，也是遞歸和迭代算法思想的典型應用場景。本文將詳細解析翻轉二叉樹的多種解法，并探討其時間復雜度和應用場景。

---

## 問題描述

**題目要求**：給定一個二叉樹的根節點 `root`，翻轉這棵二叉樹的所有左右子樹，并返回翻轉后的根節點。

**示例**：

輸入： 4 /
2 7 / \ /
1 3 6 9

輸出： 4 /
7 2 / \ /
9 6 3 1

---

## 解法一：遞歸法（DFS）

### 算法思路
遞歸是最直觀的解法，通過深度優先搜索（DFS）遍歷二叉樹的每個節點，并交換其左右子樹。

### 代碼實現
```python
def invertTree(root):
    if not root:
        return None
    # 交換左右子樹
    root.left, root.right = root.right, root.left
    # 遞歸處理左右子樹
    invertTree(root.left)
    invertTree(root.right)
    return root

復雜度分析

• 時間復雜度：O(n)，每個節點被訪問一次。
• 空間復雜度：O(h)，遞歸棧的深度取決于樹的高度（最壞情況下為O(n)）。

解法二：迭代法（BFS）

算法思路

使用廣度優先搜索（BFS）逐層遍歷二叉樹，利用隊列存儲待處理的節點，依次交換其左右子樹。

代碼實現

from collections import deque

def invertTree(root):
    if not root:
        return None
    queue = deque([root])
    while queue:
        node = queue.popleft()
        # 交換左右子樹
        node.left, node.right = node.right, node.left
        # 將子節點加入隊列
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    return root

復雜度分析

• 時間復雜度：O(n)，每個節點被訪問一次。
• 空間復雜度：O(w)，隊列的最大長度取決于樹的寬度（最壞情況下為O(n)）。

解法三：迭代法（DFS）

算法思路

通過棧模擬遞歸的深度優先搜索，顯式地控制遍歷順序。

代碼實現

def invertTree(root):
    if not root:
        return None
    stack = [root]
    while stack:
        node = stack.pop()
        # 交換左右子樹
        node.left, node.right = node.right, node.left
        # 將子節點壓入棧
        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)
    return root

復雜度分析

• 時間復雜度：O(n)。
• 空間復雜度：O(h)，棧的最大深度為樹的高度。

解法四：Morris遍歷

算法思路

Morris遍歷是一種空間復雜度為O(1)的算法，通過臨時修改樹的結構實現遍歷。

代碼實現

def invertTree(root):
    current = root
    while current:
        if current.left:
            # 找到左子樹的最右節點
            predecessor = current.left
            while predecessor.right:
                predecessor = predecessor.right
            # 將當前節點右子樹接到最右節點
            predecessor.right = current.right
            # 移動左子樹到右側
            current.right = current.left
            current.left = None
        # 移動到右子樹（原左子樹）
        current = current.right
    return root

復雜度分析

• 時間復雜度：O(n)。
• 空間復雜度：O(1)。

邊界條件與注意事項

1. 空樹處理：當輸入為 None 時直接返回。
2. 單節點樹：無需交換，直接返回根節點。
3. 性能優化：遞歸法在樹深度較大時可能導致棧溢出，迭代法更安全。

應用場景

1. 鏡像對稱樹檢測：翻轉后與原樹對比可判斷是否對稱。
2. 數據結構的教學案例：幫助理解二叉樹遍歷和指針操作。

總結

根據實際需求選擇合適的解法，遞歸法適合面試快速實現，迭代法更適合工程場景。

擴展思考

1. 如何驗證翻轉后的樹是否正確？
2. 如果要求原地修改（不新建節點），如何調整算法？
3. 非二叉樹（如三叉樹）的翻轉如何實現？

”`

（全文約1300字）