深度优先遍历：前序、中序、后序与递归迭代统一框架
摘要
二叉树专题真正的起点不是“会背三种遍历顺序”，而是理解：递归函数进入一个节点时，究竟有哪三个天然的处理时机。LeetCode 144、94、145 看似只是基础题，实际上决定了后面所有树题的思考方式。本文从递归语义出发，统一讲解前序、中序、后序三种遍历，并扩展到显式栈迭代写法，建立一套可以迁移到 二叉搜索树、树形 DP、路径问题的 DFS 框架。
第 1 章 为什么遍历顺序不是死记硬背
1.1 一个节点天然有三个处理时机
对于任意节点 root，递归函数的骨架天然是：
void dfs(TreeNode root) {
if (root == null) return;
// 时机 A：进入左子树之前
dfs(root.left);
// 时机 B：左子树处理完，右子树开始前
dfs(root.right);
// 时机 C：左右子树都处理完之后
}这三个时机对应：
| 顺序 | 访问节点的时机 | 典型用途 |
|---|---|---|
| 前序 | 进入左子树前 | 复制树、序列化、记录路径前缀 |
| 中序 | 左子树后右子树前 | 二叉搜索树 有序遍历 |
| 后序 | 左右子树都结束后 | 汇总左右子树信息、删除树、树形 DP |
所以遍历顺序的本质不是“三个词”，而是“节点处理位置”。只要这个语义想清楚，后面很多题都不再需要记模板。
1.2 为什么树题天然适合递归
因为树本身就是递归定义的：一棵树由根节点、左子树、右子树组成。你在根节点看到的结构，和你在左子树、右子树里看到的结构是同构的。换句话说，同一个函数既能解决整棵树，也能解决任意子树。
递归的关键不是“自己调自己”
真正关键是：函数的输入和输出，在子问题上保持同样语义。只要这个语义稳定，递归就成立。
第 2 章 三种递归遍历
2.1 LeetCode 144：前序遍历
前序顺序是：根、左、右。
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
dfs(root, result);
return result;
}
private void dfs(TreeNode node, List<Integer> result) {
if (node == null) {
return;
}
result.add(node.val);
dfs(node.left, result);
dfs(node.right, result);
}前序最适合“先处理当前节点，再把状态带给子节点”的场景，例如：
- 记录根到当前节点的路径前缀
- 构造树的序列化字符串
- 复制当前节点并继续复制左右子树
2.2 LeetCode 94：中序遍历
中序顺序是：左、根、右。
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
dfs(root, result);
return result;
}
private void dfs(TreeNode node, List<Integer> result) {
if (node == null) {
return;
}
dfs(node.left, result);
result.add(node.val);
dfs(node.right, result);
}中序最重要的价值在于：对 二叉搜索树 来说，它会产生严格递增序列。Validate BST、Recover BST、本专栏后面的大量搜索树题都依赖这个性质。
2.3 LeetCode 145：后序遍历
后序顺序是：左、右、根。
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
dfs(root, result);
return result;
}
private void dfs(TreeNode node, List<Integer> result) {
if (node == null) {
return;
}
dfs(node.left, result);
dfs(node.right, result);
result.add(node.val);
}后序最适合“当前节点的答案依赖左右子树答案”的场景，比如：
- 平衡二叉树 的高度计算
- 二叉树中的最大路径和
- 树的删除、释放、合并
第 3 章 迭代写法为什么容易乱
3.1 递归的本质是系统栈
递归并不神秘，它只是把“下一步去左子树还是右子树、回来后该做什么”这些控制流信息交给系统调用栈保存。改写成迭代，本质上就是你自己维护这个栈。
3.2 前序遍历的迭代写法
前序的逻辑最自然：弹出节点就访问，然后把右孩子、左孩子依次压栈。之所以先压右再压左，是因为栈后进先出，保证左子树先处理。
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) {
return result;
}
Deque<TreeNode> stack = new ArrayDeque<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
result.add(node.val);
if (node.right != null) {
stack.push(node.right);
}
if (node.left != null) {
stack.push(node.left);
}
}
return result;
}3.3 中序遍历的迭代写法
中序的难点是：节点不能在第一次遇到时立刻访问，必须一路向左下钻，直到左子树为空，再开始回退。
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode current = root;
while (current != null || !stack.isEmpty()) {
while (current != null) {
stack.push(current);
current = current.left;
}
current = stack.pop();
result.add(current.val);
current = current.right;
}
return result;
}这里的核心不是代码，而是状态语义：
current负责持续向左推进stack保存“还没访问，但左边已经处理完后需要回来访问的节点”
3.4 后序遍历的迭代写法
后序最难，因为节点必须在左右子树都处理后才能访问。常见写法有两种：
- 双栈法：一个栈做遍历，一个栈反转输出
- 单栈 +
prev指针：判断右子树是否访问过
面试里推荐先讲双栈法，逻辑更直白。
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) {
return result;
}
Deque<TreeNode> stack1 = new ArrayDeque<>();
Deque<TreeNode> stack2 = new ArrayDeque<>();
stack1.push(root);
while (!stack1.isEmpty()) {
TreeNode node = stack1.pop();
stack2.push(node);
if (node.left != null) {
stack1.push(node.left);
}
if (node.right != null) {
stack1.push(node.right);
}
}
while (!stack2.isEmpty()) {
result.add(stack2.pop().val);
}
return result;
}为什么可行？因为 根-右-左 反过来正好就是 左-右-根。
第 4 章 一个统一视角：递归函数到底该定义什么
很多人学树题越学越乱，是因为把“遍历顺序”和“函数返回值”混为一谈。更稳的方式是先问两个问题：
- 这道题要求我在遍历过程中收集什么
- 当前函数要不要给父节点返回信息
如果只是遍历收集序列，返回值可以是 void。
如果父节点需要子树高度、子树是否合法、对子树的最大贡献值，那返回值就必须承载这些信息。
遍历顺序只决定“什么时候处理当前节点”
函数返回值决定“你要把什么带回给父节点”。 这是所有树题最重要的一层抽象。
第 5 章 与后续专题的连接
5.1 前序常见延伸
5.2 中序常见延伸
5.3 后序常见延伸
- 平衡二叉树 中汇总左右高度
- 二叉树中的最大路径和 中自底向上计算“向上贡献值”
这也是为什么，尽管 144/94/145 很基础，它们却是后续所有树题的模板库。
下一篇预告
02 广度优先遍历：层序、倒序层序与锯齿层序 会把视角从“沿深度向下钻”切到“按层横向扫描”。你会看到，队列在树题里真正保存的不是节点本身，而是“当前层边界尚未处理完的工作集”。