---
title: "94. Binary Tree Inorder Traversal"
url: "https://laigary.com/interview/coding/94-binary-tree-inorder-traversal"
type: "note"
section: "coding"
date: "2023-01-29"
updated: "2026-07-28"
tags: ["Inorder Traversal", "Tree"]
---

# 94. Binary Tree Inorder Traversal

[94\. Binary Tree Inorder Traversal](https://leetcode.com/problems/binary-tree-inorder-traversal/)

中序遍歷：**先走左子樹，再處理自己，最後走右子樹**。

## 思路

三種深度優先遍歷的差別只有「處理自己」那一行放在哪，所以遞迴版三題等於一題。LeetCode 在這題的 follow-up 一樣是：

> Recursive solution is trivial, could you do it iteratively?

中序的 iterative 版是三種裡**最經典**的一個，因為它示範了「用棧模擬遞迴」的核心動作：**一路往左走到底，沿途把節點壓進棧裡**。壓進去的每個節點都代表一件待辦事項 ——「我等你的左子樹走完再處理你」。

### 為什麼中序特別重要

前序和後序都是「順序不同的走法」，但中序在 BST 上有一個特權：

> **BST 的中序遍歷結果一定是遞增序列。**

這句話是一整批題目的鑰匙。看到 BST 就先想中序，然後題目就退化成「在一個排序陣列上做事」：

- 驗證是不是 BST → 中序序列是否嚴格遞增（[98](/interview/coding/98-validate-binary-search-tree)）
- 找第 k 小 → 中序走到第 k 個就回傳（[230](/interview/coding/230-kth-smallest-element-in-a-bst)）
- 找出被交換的兩個節點 → 中序序列裡的兩個逆序對（[99](/interview/coding/99-recover-binary-search-tree)）
- 轉成排序的雙向鏈結串列 → 中序 + 一路接指標（[426](/interview/coding/426-convert-binary-search-tree-to-sorted-doubly-linked-list)）

所以這題不只是「練遍歷」，它是 BST 那一整組題的前置。整理見 [Tree 遍歷模板](/interview/coding/tree-traversal-template)。

## 解題方向

### 遞迴

```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 inorderTraversal(self, root: TreeNode) -> List[int]:
        if not root:
            return []
        res = []
        res.extend(self.inorderTraversal(root.left))
        res.append(root.val)
        res.extend(self.inorderTraversal(root.right))
        return res
```

「答案 = 左子樹的答案 + 自己 + 右子樹的答案」，直接對應定義，很好讀。但每一層都在複製子樹回傳的整個 list，複雜度會退化 —— 見下面的複雜度分析。

共用一個 `res` 的版本是嚴格 $O(n)$，也是實戰要用的形狀（因為往往要在遍歷途中做事，而不是把整個 list 拼出來）：

```python
class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        res = []

        def dfs(node):
            if not node:
                return
            dfs(node.left)
            res.append(node.val)      # 中序：處理自己夾在中間
            dfs(node.right)

        dfs(root)
        return res
```

### Iterative

```python
class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        stack = []
        cur = root

        while cur or stack:
            while cur:                 # 一路往左，沿途壓棧
                stack.append(cur)
                cur = cur.left
            cur = stack.pop()          # 最左邊還沒處理的節點
            res.append(cur.val)
            cur = cur.right            # 換到右子樹，重複同樣的事

        return res
```

三個容易卡住的地方：

- **迴圈條件是 `while cur or stack`**，兩個都要。`cur` 有東西表示還有子樹沒下潛；棧裡有東西表示還有節點等著被處理。只寫一個會提早結束。
- **`stack.pop()` 出來的節點，它的左子樹保證已經走完了** —— 因為它是在「一路往左」的過程中被壓進去的，比它更左的節點都在它上面，會先被彈出。
- **處理完之後 `cur = cur.right`**，不需要顯式回到父節點：父節點已經在棧裡等著了。

這個 `while cur: 往左壓棧` 的骨架就是「用棧模擬遞迴」的標準寫法，[173. Binary Search Tree Iterator](/interview/coding/173-binary-search-tree-iterator) 就是把它拆成 `next()` / `hasNext()` 兩個方法，本質完全一樣。

## 補充

**四種遍歷一起看**：[144. 前序](/interview/coding/144-binary-tree-preorder-traversal)（iterative 最單純）、[94. 中序](/interview/coding/94-binary-tree-inorder-traversal)、[145. 後序](/interview/coding/145-binary-tree-postorder-traversal)（iterative 最麻煩）、[102. 層序](/interview/coding/102-binary-tree-level-order-traversal)（唯一用佇列）。

**把中序當成工具的題目**：[98. Validate Binary Search Tree](/interview/coding/98-validate-binary-search-tree)、[230. Kth Smallest Element in a BST](/interview/coding/230-kth-smallest-element-in-a-bst)、[173. Binary Search Tree Iterator](/interview/coding/173-binary-search-tree-iterator)。

## 複雜度

**遞迴（`extend` 版）**
- 時間 $O(n \log n)$ ~ $O(n^2)$ — 每一層都複製子樹的 list；平衡樹是 $O(n \log n)$，**斜樹退化成 $O(n^2)$**
- 空間 $O(n)$ — 遞迴堆疊加上中途產生的暫時 list

**遞迴（共用 `res` 版）**
- 時間 $O(n)$ — 每個節點只 `append` 一次
- 空間 $O(h)$ — 只有遞迴堆疊

**Iterative**
- 時間 $O(n)$ — 每個節點進棧、出棧各一次
- 空間 $O(h)$ — 棧裡最多放一條從根往左的路徑

其中 $n$ 是節點數、`h` 是樹高（平衡樹 $O(\log n)$、斜樹 $O(n)$），都不含輸出的 `res`。

斜樹為什麼會退化：`res = 左 + [自己] + 右` 每一層都在建一個新的 list，把子樹的結果整份複製過去。左斜鏈的第 `i` 層要複製 `i` 個元素，加總起來就是 $1 + 2 + \dots + n = O(n^2)$。