94. 二叉树的中序遍历
94. 二叉树的中序遍历
简单
给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。
示例 1：
输入：root = [1,null,2,3]
输出：[1,3,2]示例 2：
输入：root = []
输出：[]示例 3：
输入：root = [1]
输出：[1]
提示：
- 树中节点数目在范围
[0, 100]内 -100 <= Node.val <= 100
进阶: 递归算法很简单，你可以通过迭代算法完成吗？
这是为您定制的 二叉树的中序遍历 (递归法 / DFS) 复习笔记。
欢迎正式进入 二叉树 (Binary Tree) 的世界！ 这份代码是二叉树遍历的 “母题”。虽然递归写法只有寥寥几行，但它是理解 DFS (深度优先搜索) 的基石。您注释里提到的“代码移到前面/后面就是前/后序”，一语道破了 DFS 的天机。
📝 核心笔记：二叉树的中序遍历 (Inorder Traversal)
1. 核心思想 (一句话总结)
“左 -> 中 -> 右：先一路走到最左下角，打印出来，退回一步打印中间，再去右边转转。”
- 前序 (Pre-order)：根 -> 左 -> 右 (先办事，再跑腿)
- 中序 (In-order)：左 -> 根 -> 右 (先跑到底，回来办事，再继续跑)
- 后序 (Post-order)：左 -> 右 -> 根 (最后办事)
2. 核心特性 (BST 的秘密)
中序遍历有一个 价值连城的特性，请务必刻在脑海里：
如果是 二叉搜索树 (BST)，中序遍历的结果是一个 升序数组。 很多验证 BST、找 BST 第 K 小元素的题目，本质上就是考中序遍历。
3. 算法流程 (递归视角)
- 终止条件：
node == null，没路了，返回。 - 递归左子树：
dfs(node.left)。相信这个函数能把左边全搞定。 - 处理当前节点：
ans.add(node.val)。 - 递归右子树：
dfs(node.right)。相信这个函数能把右边全搞定。
🔍 代码回忆清单
// 题目：LC 94. Binary Tree Inorder Traversal
class Solution {
public List inorderTraversal(TreeNode root) {
List ans = new ArrayList<>();
dfs(ans, root);
return ans;
}
private void dfs(List ans, TreeNode node) {
// 1. Base Case: 撞墙回头
if (node == null) {
return;
}
// 2. 递归去左边 (L)
dfs(ans, node.left);
// 3. 处理中间 (Root) - 中序的位置
ans.add(node.val);
// 4. 递归去右边 (R)
dfs(ans, node.right);
}
} ⚠️ 面试高频扩展 (Iterative / 迭代法)
面试官经常会问：“如果递归栈溢出怎么办？能不能用迭代（栈）来实现？” 这是为了考察你对 “系统调用栈” 的模拟能力。
核心逻辑：
- 一路向左：把沿途经过的节点全都压入栈 (
push)，直到走到null。 - 到头回退：从栈里弹出一个节点 (
pop)，这个节点就是当前的“左下角”或“根”。 - 记录并转向：记录它的值，然后让指针指向它的 右孩子 (
node = node.right)。
// 迭代法模版 (一定要背下来)
public List inorderTraversal(TreeNode root) {
List res = new ArrayList<>();
Deque stack = new ArrayDeque<>();
// 指针 cur 从 root 开始
TreeNode cur = root;
// 只要 cur 还有路走，或者栈里还有存货，就继续
while (cur != null || !stack.isEmpty()) {
// 1. 既然非空，就一路向左，把沿途的都压进去
if (cur != null) {
stack.push(cur);
cur = cur.left;
}
// 2. 走到头了 (cur == null)，开始弹栈
else {
cur = stack.pop(); // 弹出栈顶元素
res.add(cur.val); // 【中序】在这里记录值
cur = cur.right; // 转向右子树
}
}
return res;
} 🖼️ 数字演练
树结构：
1
/
2 3递归视角：
dfs(1)调用dfs(2)。dfs(2)调用dfs(null)(左)，返回。dfs(2)添加 2。dfs(2)调用dfs(null)(右)，返回。dfs(2)结束，回到dfs(1)。dfs(1)添加 1。dfs(1)调用dfs(3)。dfs(3)添加 3。
结果：[2, 1, 3]
