二叉树遍历

二叉树遍历是面试中最常考的数据结构题。面试官想看到你不只是会背模板，而是真正理解递归的本质和树的遍历顺序。

面试考察点

面试官通过这道题想考察：
1. 你是否理解递归的本质——为什么递归能遍历树
2. 你是否能说清三种遍历顺序的区别
3. 你是否能从递归理解迭代——为什么可以用栈模拟递归
4. 你是否理解遍历的实际应用场景

---

一、树的递归结构

1.1 什么是递归定义？（小白也能懂）

面试官追问："什么是递归？树为什么能用递归遍历？"

递归就是"自己调用自己"。

树为什么能用递归？
因为树的定义本身就是递归的！

树的递归定义：
一棵树 = 一个根节点 + 若干子树
每个子树 = 一个根节点 + 若干子子树
...

看一个具体的树：

         A（根节点）
        / \
       B   C（子树）
      /   / \
     D   E   F（子子树）

树 A 包含子树 B、C
子树 B 包含节点 D
子树 C 包含节点 E、F

所以遍历树 A：
1. 先处理 A
2. 再遍历子树 B（这本身是一棵树）
3. 再遍历子树 C（这本身也是一棵树）

递归遍历子树时，逻辑和遍历整棵树完全一样！
这就是为什么递归天然适合树。

1.2 树的三种遍历顺序

面试官追问："前序、中序、后序遍历有什么区别？"

以这个树为例：

         1
        / \
       2   3
      / \
     4   5

三种遍历顺序的"处理时机"：

前序（Pre-order）：根 → 左 → 右
处理根的时机：第一次见到就处理

遍历过程：
1. 到达节点1 → 处理1（输出）
2. 去左子树
3. 到达节点2 → 处理2（输出）
4. 去节点2的左子树
5. 到达节点4 → 处理4（输出）
6. 节点4左右都空，返回
7. 到达节点5 → 处理5（输出）
8. 节点5左右都空，返回
9. 节点2左右都空，返回
10. 去节点1的右子树
11. 到达节点3 → 处理3（输出）
12. 节点3左右都空，返回

输出：1 → 2 → 4 → 5 → 3

中序（In-order）：左 → 根 → 右
处理根的时机：第二次见到（从左子树返回时）处理

遍历过程：
1. 到达节点1
2. 去左子树
3. 到达节点2
4. 去节点2的左子树
5. 到达节点4
6. 节点4左右都空 → 处理4（输出）→ 返回
7. 返回到节点2 → 处理2（输出）
8. 去节点2的右子树
9. 到达节点5
10. 节点5左右都空 → 处理5（输出）→ 返回
11. 返回到节点1 → 处理1（输出）
12. 去节点1的右子树
13. 到达节点3 → 处理3（输出）

输出：4 → 2 → 5 → 1 → 3

面试追问：中序遍历二叉搜索树会怎样？
回答：得到升序排列！这很有用！

后序（Post-order）：左 → 右 → 根
处理根的时机：最后一次见到（左右子树都处理完）处理

遍历过程：
1. 到达节点1
2. 去左子树
3. 到达节点2
4. 去节点2的左子树
5. 到达节点4
6. 节点4左右都空 → 返回
7. 去节点2的右子树
8. 到达节点5
9. 节点5左右都空 → 返回
10. 节点2左右子树处理完 → 处理2（输出）→ 返回
11. 去节点1的右子树
12. 到达节点3
13. 节点3左右都空 → 处理3（输出）→ 返回
14. 节点1左右子树处理完 → 处理1（输出）

输出：4 → 5 → 2 → 3 → 1

面试追问：后序遍历有什么用？
回答：释放树（先释放子树再释放根）、计算后缀表达式

1.3 三种遍历的对比

┌──────────────────────────────────────────────────────┐
│  遍历顺序对比（以上面的树为例）                        │
├──────────────────────────────────────────────────────┤
│  前序：1 → 2 → 4 → 5 → 3                              │
│  中序：4 → 2 → 5 → 1 → 3                              │
│  后序：4 → 5 → 2 → 3 → 1                              │
├──────────────────────────────────────────────────────┤
│  应用场景：                                           │
│  前序：树的复制/序列化、获取根节点优先的处理           │
│  中序：二叉搜索树排序（升序）                         │
│  后序：树的删除（先删子树再删根）、依赖分析           │
└──────────────────────────────────────────────────────┘

---

二、递归遍历的原理

2.1 递归调用栈的真相（面试核心）

面试官追问："递归遍历时，到底发生了什么？"

递归遍历的调用栈：

以中序遍历为例：

inorder(root)
    ↓
inorder(root.left)          ← 调用自己（压栈）
    ↓
inorder(node.left)          ← 再调用（再压栈）
    ↓
inorder(null)               ← 遇到空，返回（弹栈）
    ↓
处理 node                 ← 返回后处理
    ↓
inorder(node.right)         ← 处理完左，处理右
    ...

调用栈变化：
Push → Push → Push → Pop → Pop → 处理 → Push → ...

面试加分点：能画出递归调用图！

中序遍历的递归调用图：

调用 inorder(1)
    │
    ├── 调用 inorder(2)
    │       │
    │       ├── 调用 inorder(4)
    │       │       │
    │       │       └── 调用 inorder(null) → 返回
    │       │       处理 4
    │       └── 调用 inorder(null) → 返回
    │
    ├── 处理 2
    │
    └── 调用 inorder(5)
            │
            └── 调用 inorder(null) → 返回
            处理 5
            调用 inorder(null) → 返回
    │
    处理 1
    │
    └── 调用 inorder(3)
            ...

2.2 为什么递归可以用栈模拟？（理解迭代）

面试官追问："递归和迭代哪个好？能不能把递归改成迭代？"

递归的本质是什么？
是"调用栈"——系统帮你管理"该去哪里"的上下文。

递归版本的问题：
- 栈深度受限制（递归太深会栈溢出）
- 函数调用有开销

迭代版本的原理：
既然递归是调用栈，那我手动用一个栈来模拟不就行了？

递归版：
function inorder(node) {
    if (!node) return;
    inorder(node.left);   // 调用自己
    处理 node;
    inorder(node.right);  // 调用自己
}

迭代版：
function inorderIterative(node) {
    stack = []
    while (stack.length > 0 || node) {
        // 一直往左走，把节点压栈
        while (node) {
            stack.push(node);
            node = node.left;
        }

        // 弹出节点，处理
        node = stack.pop();
        处理 node;

        // 转向右子树
        node = node.right;
    }
}

两者是等价的！
递归是"隐式"的调用栈
迭代是"显式"的调用栈

---

三、层序遍历（广度优先）

3.1 什么是层序遍历？

面试官追问："什么是 BFS？为什么用队列？"

层序遍历：按层级访问节点

         1        ← 第1层
        / \
       2   3     ← 第2层
      / \   \
     4   5   6   ← 第3层

层序遍历结果：1 → 2 → 3 → 4 → 5 → 6

关键点：需要"按层"，不能跳着访问

怎么做到？
用队列！先进先出！

第一轮：处理第1层，同时把第2层入队
第二轮：处理第2层，同时把第3层入队
...

这就像排队叫号：
先叫到的先处理，处理完再叫下一批

3.2 层序遍历的变形（面试高频）

锯齿形遍历（LeetCode 103）：

要求：第一层左到右，第二层右到左，第三层左到右...

结果：1 → 3 → 2 → 4 → 5 → 6

怎么实现？
- 正常层序遍历
- 但根据层数决定是从左还是从右添加结果

按层记录（LeetCode 102）：

要求：不仅遍历，还要把每层的节点分开

结果：[[1], [2,3], [4,5,6]]

关键：在处理每层前，先记录当前队列的大小（这层的节点数）

---

四、面试真题讲解

题目1：验证二叉搜索树（LeetCode 98）

考察点：BST 的性质 + 中序遍历的应用

BST 的性质：
- 左子树所有节点 < 根节点
- 右子树所有节点 > 根节点
- 左右子树也是 BST

关键洞察：中序遍历 BST 会得到升序序列！

验证方法：
1. 中序遍历 BST
2. 检查遍历结果是否严格递增（不是>=，是>）
3. 如果是升序，说明是 BST

面试追问：为什么是严格递增？
回答：因为 BST 定义是左<根<右，不能有相等的值

题目2：二叉树的最近公共祖先（LeetCode 236）

考察点：递归的巧妙应用

问题：找两个节点的最近公共祖先

核心思想（递归）：
1. 如果当前节点是 p 或 q，返回当前节点
2. 在左子树找，如果在右子树也找到，当前节点就是 LCA
3. 如果只在一边找到，就返回那边的结果

为什么对？
因为最近公共祖先的特点是：
- p 和 q 分别在它的左右子树（或者它自己就是其中一个）
- 这正是递归函数返回非空值的条件！

题目3：二叉树展开为链表（LeetCode 114）

考察点：后序遍历的应用

问题：把二叉树变成"只有右子树的链表"

     1              1
    / \              \
   2   5    →        2
  / \                \
 3   4                3
                      \
                       4
                        \
                         5

关键洞察：后序遍历（左右根）最后处理根！

解法：
1. 后序遍历，先把左右子树拉平成链表
2. 把左链表接到根的右边
3. 把右链表接到左链表的末尾

---

五、面试总结

核心概念

┌─────────────────────────────────────────────────────┐
│                   二叉树遍历                         │
├─────────────────────────────────────────────────────┤
│                                                     │
│   前序（根左右）：复制树、序列化、拓扑排序           │
│   中序（左右根）：BST 排序、后缀表达式               │
│   后序（左右根）：释放树、依赖分析                   │
│   层序（BFS）：最短路径、按层处理                    │
│                                                     │
│   递归的本质 = 调用栈 = 隐式管理上下文                │
│   迭代 = 手动用栈模拟                                │
│                                                     │
└─────────────────────────────────────────────────────┘

面试高频追问

面试能加分的回答

1. 能画出递归调用图
   "我可以用图来表示递归的调用顺序"

2. 能解释递归和迭代的关系
   "递归是隐式的调用栈，迭代是显式的"

3. 能说明遍历的实际应用
   "前序用于复制树，后序用于释放内存"

4. 能推导 BST 中序有序的性质
   "BST 定义决定中序遍历是升序"

---

相关题目

• LeetCode 98 - 验证二叉搜索树 - BST 性质
• LeetCode 236 - 二叉树的最近公共祖先 - 递归应用
• LeetCode 102 - 二叉树的层序遍历 - BFS
• LeetCode 114 - 二叉树展开为链表 - 后序应用