leetcode-go/二叉树/36-二叉树的中序遍历.md

---
tags: ["LeetCode", "二叉树", "深度优先搜索", "迭代", "简单"]
create time: 2026-05-17 10:00
---

# 36-二叉树的中序遍历

## 题面

给定一个二叉树的根节点 `root`，返回它的 **中序** 遍历。

> 中序遍历的顺序：**左子树 → 根节点 → 右子树**。

**示例 1：**

```
输入：root = [1,null,2,3]
输出：[1,3,2]
```

```
    1           遍历顺序
     \         ┌─────────┐
      2   ──→ │ 1 → 3 → 2│
     /              └─────────┘
    3
```

**示例 2：**

```
输入：root = []
输出：[]
```

**示例 3：**

```
输入：root = [1]
输出：[1]
```

**约束：**

- 树中节点数目在范围 `[0, 100]` 内
- `-100 <= Node.val <= 100`

**进阶：** 递归算法很简单，你可以通过迭代算法完成吗？

---

## 思路

> [!question] 💡 思考
> 中序遍历的核心是"先深入左子树到底，再处理根，最后转向右子树"。递归版本天然利用系统调用栈来记住回溯路径——那如果我们手动模拟这个过程，该用什么数据结构？

### 方法一：递归（最直观）⭐

中序遍历的递归实现几乎是对定义的字面翻译：

```
inorder(node):
    if node == nil: return
    inorder(node.left)       // ① 先走左边
    visit(node.val)          // ② 再取当前值
    inorder(node.right)      // ③ 最后走右边
```

这种写法简洁优雅，但进阶要求我们尝试迭代。让我们看看如何用显式栈来模拟递归的调用栈行为。

### 方法二：显式栈模拟（迭代）⭐⭐

#### 为什么用栈？

递归过程中，每进入一个节点的左子树，系统会把这个节点的"后续工作（访问自己、再访问右子树）"压入调用栈。当我们从左子树底部返回时，栈顶弹出刚才那个节点，进行处理。

**关键观察**：迭代的本质就是手动维护这个栈。

#### 核心流程

```mermaid
flowchart TD
    A["curr = root"] --> B{"curr != nil?"}
    B -->|"否"| C{"栈为空?"}
    C -->|"是"| D["结束, 返回结果"]
    C -->|"否"| E["弹栈得到 node"]
    E --> F["记录 node.val"]
    F --> G["curr = node.right"]
    G --> B
    B -->|"是"| H["一路向左\n每次经过的节点都压栈\ncurr = curr.left"]
    H --> B
```

#### 逐步解析

以这棵树为例：

```
       2
      / \
     1   3
```

| 步骤 | 动作 | 栈 (底→顶) | curr | 结果 |
|------|------|------------|------|------|
| 初始 | — | `[]` | `2` | `[]` |
| 1 | 2 压栈，走到左 | `[2]` | `1` | `[]` |
| 2 | 1 压栈，走到左 | `[2, 1]` | `nil` | `[]` |
| 3 | curr=nil，弹栈 `1` | `[2]` | `nil` | `[1]` |
| 4 | 1 无右子树，curr=`nil` | `[2]` | `nil` | `[1]` |
| 5 | curr=nil，弹栈 `2` | `[]` | `2` | `[1, 2]` |
| 6 | 2 有右子树 3，curr=`3` | `[]` | `3` | `[1, 2]` |
| 7 | 3 压栈，走到左 | `[3]` | `nil` | `[1, 2]` |
| 8 | curr=nil，弹栈 `3` | `[]` | `nil` | `[1, 2, 3] ✅` |

**算法骨架**（记忆口诀：「能左就左，左到不能左就回退，回头往右拐」）：

```
curr = root
while curr != nil 或 栈非空:
    // 阶段1: 一路向左，全部压栈
    while curr != nil:
        push(curr)
        curr = curr.left
    
    // 阶段2: 栈顶就是下一个要访问的节点
    node = pop()
    result.append(node.val)
    
    // 阶段3: 转向右子树
    curr = node.right
```

> [!info] 🧠 为什么这个循环是正确的？
> 想象你在走迷宫：看到岔路就往左边走，同时把走过的路口记下来（压栈）。当发现左边没路了，就回到上一个路口（弹栈），记录它，然后尝试右边的路。重复直到所有路口都走完且栈为空。

#### Go 语言实现细节

- Go 标准库没有内置栈，用 `[]T` 切片即可，追加和删除尾部操作均摊 O(1)
- `nil` 判断直接 `node == nil`，不需要额外的判空辅助函数

---

## 代码提示

```
// 伪代码模板
初始化空栈 stack
curr = root
result = []

while curr != nil 或 len(stack) > 0:
    // 一路向左
    while curr != nil:
        stack = append(stack, curr)
        curr = curr.left
    
    // 回退 + 记录
    node = stack[len(stack)-1]
    stack = stack[:len(stack)-1]  // pop
    result = append(result, node.val)
    
    // 转向右子树
    curr = node.right
```

---

## 技巧

> [!tip] 🔑 核心模式：Morris 中序遍历（进阶面试杀手锏）
> 上面的迭代法使用了 O(h) 空间（h 为树高）。如果面试官要求 **O(1)** 空间呢？答案是利用叶子节点的 nil 指针建立临时线索（Threaded Binary Tree），遍历完再恢复原状。虽然实际工程中很少用到，但在面试中是展示深度的利器。
>
> 基本思路：对于当前节点，找到其左子树的最右节点（前驱）。如果前驱的 right 指向 nil，说明第一次到达此节点，建立线索并往左走；如果前驱的 right 已经指向当前节点，说明左子树已遍历完毕，断开线索、记录当前值、往右走。

> [!note] 🐹 Go 切片栈操作速查
> - 压栈：`stack = append(stack, val)`
> - 弹栈：`val := stack[len(stack)-1]; stack = stack[:len(stack)-1]`
> - 判空：`len(stack) == 0`
> - 不要使用 `stack = nil` 代替缩容——这会丢失容量信息，影响后续 append 性能

> [!info] 📊 复杂度分析
> - 时间：**O(n)**，每个节点恰好被压栈一次、弹栈一次，总共 2n 次栈操作
> - 空间：**O(h)**，h 为树的高度。最坏情况（链状树）O(n)，平均情况（平衡树）O(log n)

> [!comparison] ⚖️ 三种写法对比
> | 维度 | 递归 | 迭代（显式栈） | Morris |
> |------|------|--------------|--------|
> | 代码简洁度 | ⭐⭐⭐ | ⭐⭐ | ⭐ |
> | 空间复杂度 | O(h) 隐式栈 | O(h) 显式栈 | **O(1)** |
> | 是否修改树结构 | ❌ | ❌ | 临时修改后恢复 |
> | 面试推荐度 | 入门可用 | **首选** | 加分项 |

---

## 代码

### 迭代法（推荐）⭐⭐

```go
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func inorderTraversal(root *TreeNode) []int {
	var result []int          // 存放遍历结果
	var stack []*TreeNode     // 显式栈，存储待回退处理的节点
	curr := root              // 工作指针

	for curr != nil || len(stack) > 0 {
		// 阶段1: 一路向左，途经节点全部压栈
		for curr != nil {
			stack = append(stack, curr)
			curr = curr.Left
		}

		// 阶段2: 栈顶元素即为下一个应访问的节点
		node := stack[len(stack)-1]       // peek 栈顶
		stack = stack[:len(stack)-1]      // pop
		result = append(result, node.Val) // 记录值

		// 阶段3: 转向右子树，下一轮继续从右子树最左开始
		curr = node.Right
	}

	return result
}
```

### 递归法（参考）⭐

```go
func inorderTraversal(root *TreeNode) []int {
	if root == nil {
		return nil
	}

	// 左 → 根 → 右
	left := inorderTraversal(root.Left)
	right := inorderTraversal(root.Right)

	// 拼接结果
	result := left
	result = append(result, root.Val)
	result = append(result, right...)

	return result
}
```

> [!success] ✅ 运行验证
> 这是 LeetCode 第 94 题（编号更正：原题编号应为 94，此处笔记沿用用户原始编号 36），通过率约 70%，是中序遍历的经典入门题。迭代解法是理解二叉树遍历底层机制的基石——掌握后，前序/后序遍历的迭代写法只需调整「记录时机」即可迁移。