---
title: "226. Invert Binary Tree"
url: "https://laigary.com/interview/coding/226-invert-binary-tree"
type: "note"
section: "coding"
date: "2023-01-29"
updated: "2026-07-28"
tags: ["Tree", "Depth-First Search"]
---

# 226. Invert Binary Tree

[226. Invert Binary Tree](https://leetcode.com/problems/invert-binary-tree/)

把二元樹左右翻轉（每個節點的左右子樹對調）。

## 思路

「翻轉整棵樹」聽起來要做很多事，但用遞迴的角度看只有一句話：

> **每個節點都把自己的左右子樹交換就好。**

因為交換是對每個節點獨立的動作，遞迴下去自然就會把整棵樹都翻完。不需要先想「整體變成什麼樣」，只要想「站在一個節點上我該做什麼」—— 這是樹遞迴最重要的思考方式。

`base case` 是空節點：什麼都不用做，直接回傳。回傳 `root`（也就是 `None`）而不是硬回傳 `None`，是為了讓上一層可以直接把回傳值接上去。

**前序還是後序都可以**，這題是少數兩者皆可的例子 —— 因為「交換左右指標」和「處理子樹」互不影響。先交換再遞迴（前序）或先遞迴再交換（後序）結果一樣。

## 解題方向

```python
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if not root:
            return root
        root.left, root.right = self.invertTree(root.right), self.invertTree(root.left)
        return root
```

這一行同時做完了遞迴和交換，關鍵在 Python 的**多重賦值會先把右邊整個算完再一次寫入**。所以 `self.invertTree(root.right)` 和 `self.invertTree(root.left)` 都是對**還沒被修改的**原始子樹呼叫的，不會互相污染。

如果拆成兩行寫就會出事：

```python
        root.left = self.invertTree(root.right)     # root.left 被蓋掉了
        root.right = self.invertTree(root.left)     # 這裡的 root.left 已經是新的了
```

第二行拿到的 `root.left` 已經是剛才寫入的值，等於把同一邊翻了兩次。**要拆行就得先存起來**：

```python
        left, right = root.left, root.right
        root.left = self.invertTree(right)
        root.right = self.invertTree(left)
```

「先存後改」跟鏈結串列題是同一個通則 —— 只要一個賦值會蓋掉等下還要用的東西，就先存起來。

## 補充

**這題有名的原因**是 [Homebrew 作者發過一則推文說 Google 因為他不會在白板上翻轉二元樹而拒絕了他](https://x.com/mxcl/status/608682016205344768?s=20)。所以它常被當成「基本功檢查」，重點不在難度，而在**能不能乾淨俐落地寫出來並解釋清楚**。

**迭代版**只要把任何一種遍歷的「處理節點」換成交換就好，例如用佇列：

```python
        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
```

因為交換與遍歷順序無關，所以 BFS、前序、後序都行 —— 這也回頭印證了上面說的「這題前後序皆可」。

**相關題**：[100. Same Tree](/interview/coding/100-same-tree)（同步比較兩棵樹；把一棵翻轉後再比就是判斷對稱）、[114. Flatten Binary Tree to Linked List](/interview/coding/114-flatten-binary-tree-to-linked-list)（同樣是原地改指標，但順序有講究）。整理見 [Tree 遍歷模板](/interview/coding/tree-traversal-template)。

## 複雜度

- 時間 $O(n)$ — 每個節點交換一次
- 空間 $O(h)$ — 遞迴堆疊，`h` 是樹高（BFS 版則是 $O(w)$，`w` 是最寬一層的節點數）

其中 `n` 是節點數。平衡樹的 `h` 是 $O(\log n)$、退化成鏈時是 $O(n)$。