树系列第 5 篇：深度优先遍历——前序、中序、后序

欢迎来到“树系列”第 5 篇。前面的四篇文章，我们先把树“长什么样”研究透了：第 1 篇回答了“为什么需要树”，第 2 篇把节点、边、根、叶子、深度、高度这些术语一个个讲明白，第 3 篇把孩子的数量限制成最多两个，认识了二叉树以及满二叉树、完全二叉树，第 4 篇则把树放进了内存，比较了链式存储、数组存储、双亲表示法和孩子兄弟表示法的代价。可以说，树已经“住”进我们的代码里了。但住进去不等于会用。就像搬家之后，你还需要在屋子里走一圈，把每个房间都看一遍，才知道东西放在哪儿；一棵树如果只是静静躺在内存里，不把它的每个节点都走一遍，我们就永远不知道里面有什么。这一趟“把每个节点都走一遍”的旅程，就叫遍历。

本篇是“树系列”真正的分水岭。从这一篇开始，树不再是一张静态的图，而是一个会“动”的结构：我们学习如何系统地访问它、搜索它、改造它。本篇专注在**深度优先遍历（Depth-First Traversal）**的三种形式——前序遍历、中序遍历、后序遍历。它们被统称为深度优先家族的三种“姿势”，也是后续二叉搜索树、堆、平衡树、序列化等内容的基本功。读完本篇，你将会得到：第一，一句口诀——“根的位置决定名字”，从此三种遍历的名字不再靠死记硬背；第二，一棵树从头走到尾的完整手算过程，每一步都标上访问序号；第三，递归背后的调用栈展开图，明白递归凭什么能“记住回头路”；第四，三种不用递归的迭代写法，看清显式栈和函数调用栈其实是同一件事；第五，时间与空间复杂度分析；最后，一组经典应用：表达式树求值、复制树、序列化与反序列化，以及目录遍历。如果你在查找实验室里玩过二叉搜索树的查找，会发现查找路径本质上就是一次“定向遍历”——从根出发，每走一步就决定往左还是往右，最终停在目标节点上。本篇会把这种“走”的系统化方法彻底讲透。

0 先把前四篇的结论捡回来

在正式出发之前，先花一小节把前面的装备清点一遍。第一，树是什么：树由节点和连接节点的边组成，有一个唯一的根节点，除根之外每个节点都有且只有一个父亲；没有孩子的节点叫叶子；从某个节点往下看，它和它的全部后代合在一起叫子树。第二，深度与高度：一个节点的深度是从根走到它所经过的边数，根节点的深度是 0；一棵树的高度是从根到最远叶子的边数，这个“最远”决定了深度优先遍历最坏要走多深。第三，二叉树：每个节点最多有两个孩子，并且孩子的左右是有区别的——左孩子和右孩子是两个不同的位置，即使某个位置空着，它依然存在。二叉树本身可以递归定义：二叉树要么是空树，要么由一个根节点和左右两棵子树构成，左右子树仍然是二叉树。这个递归定义不是文字游戏，它是本篇所有递归算法的“源代码”：前序、中序、后序三种遍历的递归写法，几乎就是把这句定义翻译成代码。第四，存储：第 4 篇讲过，二叉树最常用的存储方式是链式存储，每个节点保存自己的值、左孩子指针和右孩子指针；数组存储则把父子关系变成下标公式。本篇的代码统一使用链式存储的视角，但请记住：遍历关心的是“沿着边从节点走到节点”，与具体存储实现无关。你在数组存储上同样可以做前序、中序、后序遍历，只是“走到孩子”的动作从“读指针”变成了“算下标”。

还有一个必须提前说清的约定：本篇讨论的遍历都发生在二叉树上。多叉树也有深度优先遍历，思想完全一样，只是“先左后右”变成“按孩子顺序依次访问”；本篇之所以聚焦二叉树，是因为前序、中序、后序这三个词在二叉树语境下定义最干净，也是面试与竞赛里出现频率最高的形式。等把二叉树吃透，多叉树只是换皮不换骨。

1 什么是遍历：把每个节点都访问一遍

“遍历”这个词听起来很学术，其实意思极其朴素：把一棵树里的所有节点，一个不漏地访问一遍。就像点名一样，每个节点都要被叫到，不能重复，也不能漏掉。这里的“访问”是一个抽象动作，具体做什么由你决定：可以是打印节点的值，可以是把节点的值累加起来，可以是统计叶子数量，可以是修改节点里的数据，也可以是把节点写进文件。不同的任务只改变“访问”这个动作的内容，不改变“怎么安排访问顺序”这件事本身。

那为什么访问顺序还有讲究？有人可能会想：反正每个节点都要访问一次，先访问谁后访问谁，结果不都一样吗？这个想法对“把节点的值全部加起来”这种任务成立——加法满足交换律，先加谁后加谁，总和不变。但对很多任务，顺序至关重要。举个最直观的例子：一棵二叉搜索树，如果我们想按从小到大的顺序把值打印出来，就必须采用“左子树、根、右子树”的顺序，用其他顺序打印出来就是乱序的。再比如把树写进文件做序列化，访问顺序决定了文件内容的格式，反序列化时必须用完全相同的规则才能把树还原。还比如表达式树求值，必须先把左右子树的值算出来，才能计算根节点代表的运算符，顺序错了，结果就是错的。所以，“访问顺序”不是遍历的副产品，而是遍历的灵魂。

遍历在实现层面只有两类“走法”。第一类叫深度优先：像探险家一样，从根出发，沿着一条路一直往深处走，走到走不动了，再退回来换一条路继续走；第二类叫广度优先：像一层一层扫楼一样，先把第一层所有节点访问完，再访问第二层，再访问第三层。本篇讲深度优先，第 6 篇讲广度优先。理解这两类的区别，对后续所有树形算法都至关重要。

下面这棵树（以后叫它“示例树”）将贯穿全篇，作为手算的公共画布：

空子树的位置不是装饰：遍历时一旦遇到空指针就立即返回，这正是递归代码里唯一的终止条件。后面三张手算图都从这棵树演变出来。

示例树一共有 7 个节点：根是 A，A 的左孩子是 B、右孩子是 C；B 的左孩子是 D、右孩子是 E；C 的右孩子是 F（C 没有左孩子）；E 的左孩子是 G（E 没有右孩子）。叶子一共有三片：D、F、G。这棵树故意设计得”不太对称”，左边深、右边浅，还让 C 缺了左孩子、让 E 缺了右孩子。这样设计是有用意的：遍历手算时，缺位的地方恰恰是最容易出错的地方，我们必须搞清楚”空子树”在遍历里意味着什么。请把这张图记在心里，接下来的三个小节的每一张手算图，都是从它演变出来的。

遍历还有一个重要的“好消息”：树是没有环的。图结构里可能有环，遍历时如果不做标记，很容易兜圈子，永远走不完；而树的任意两个节点之间，路径都是唯一的，从根出发到任何一个节点，只有一条路可走。这意味着，只要我们在树里沿着边往下走，就不可能绕回已经走过的节点。正是这个性质，让树的遍历可以做得“轻”：不需要额外的 visited 标记，不需要记录哪些节点已经去过，只要安排好递归或栈的节奏，每个节点天然只会被经过有限次。这一点看似微不足道，却是树比图好对付的根本原因之一。

2 深度优先思想：先走到最深，再回头

深度优先这名字取得非常诚实：优先保证“深度”。具体来说，从根节点出发，每当面对“去哪个孩子”的选择时，深度优先的策略是：先选一个方向（约定先左后右）一直走下去，走到叶子——也就是再也没有孩子可走的地方——才停下来，然后掉头往回走，回到上一个岔路口，换另一个方向继续。整个过程就像在迷宫里用“右手贴墙”的规则走路：一条道走到黑，撞了南墙再回头。

“深度”这个词在这里不是装饰。一个节点的深度，是它到根的距离；深度优先遍历的“优先”，指的是它总是先把当前分支的深度拉满，再去管同一层的兄弟。你可以这样感受：如果把树比作一座迷宫，深度优先是“一探到底”的探险家，广度优先是“层层平推”的扫描仪。探险家的好处是：只需要记住一条回头路（当前走过的路径），就能完整地走完整个迷宫；缺点则是，如果目标藏得很浅，他却可能先在深沟里浪费很长时间。扫描仪正好相反。这两种风格没有绝对优劣，只有适用场景。

在示例树上，“一条道走到黑”具体是什么感觉？从根 A 出发，先走左孩子 B，再走 B 的左孩子 D。D 是叶子，无路可走，于是回头到 B，再走 B 的右孩子 E，接着走 E 的左孩子 G。G 是叶子，再回头到 E、到 B、到 A，然后走 A 的右孩子 C，再走 C 的右孩子 F。F 是叶子，回头到 C、到 A，整棵树走完。注意这条路线里的一个细节：A 不是一步就走到最深的，而是先到了 B，B 又替它往下走；每一次“往下走一格”，都等于把当前这个子树看成一个新的起点。这种“把子树当作新树”的眼光，正是递归的思想基础，我们马上会在代码里看到它。

下面这张图把“一路走到最深，再一层层回头”的路线画了出来。实线是前进的方向，虚线是回头的方向：

回头是深度优先的关键动作：每次掉头都意味着当前分支已经彻底走完，接下来只会去兄弟方向，绝不会重新访问已走过的节点。这就是它不需要 visited 标记也能不重不漏的原因。

深度优先遍历之所以不会重复访问、也不会漏掉节点，靠的是两条纪律。第一，约定方向：每次面对孩子，都严格按同一个顺序选择，比如先左后右，这样每一次选择都是确定的，整个遍历过程可以被复制，别人照做会得到一模一样的结果；第二，只往前看：从一个节点往下走时，只沿着它的孩子走，绝不”横跳”到它的兄弟，兄弟要等回到共同父亲时才会轮到。这两条纪律合起来，保证了对任意一棵二叉树，从根出发的深度优先走法只有一种标准走法，不会因为心情不同而走出不同路线。当然，如果你把”先左后右”整体换成”先右后左”，得到的是一棵镜像树的遍历结果，本质上是同一件事，本篇统一采用先左后右。

其实深度优先遍历里还藏着一个更细的层次：同一棵子树，你在“什么时候”访问它的根，决定了遍历叫什么名字。走到一个节点时，你会有三个自然的“时间点”：刚到达它时（还没去左孩子）、从左子树回来时（左孩子已经看完）、从右子树回来时（全部看完）。在第一个时间点访问，就是前序；在第二个时间点访问，就是中序；在第三个时间点访问，就是后序。这个“三次经过”的视角是第 6 章的重点，现在先在心里留个钩子，等我们分别看完三种遍历，再回来看这个统一的视角。

3 前序遍历：根 → 左 → 右

3.1 定义与口诀

前序遍历的规则只有一句话：先访问根节点，再遍历左子树，最后遍历右子树。口诀就是三个字——“根左右”。这里的“左”和“右”不是指单个的左孩子和右孩子，而是指“整棵左子树”和“整棵右子树”；而子树内部，又继续执行同样的规则：子树的根先访问，再走它的左子树，再走它的右子树。换句话说，前序遍历对“先访问根”这件事最执着，走到任何一个节点，第一件事就是访问它，然后才轮到它的后代。

注意“根左右”里藏着一个容易忽略的点：当左子树是一棵空树时，“根左右”就变成了“根右”——先访问根，然后发现没有左子树可走，就直接进入右子树。当左右子树都是空时，前序遍历对一个节点的处理就只剩“访问它自己”这一件事，然后立即返回。这就是为什么前序遍历对叶子节点的处理最简单：叶子没有任何后代，访问完自己，整棵子树就结束了。千万别小看“空子树”这个边界，递归代码里所有的 if 判断、所有的终止条件，其实都是在处理“空”这件事。

3.2 手算例子：把示例树完整走一遍

理论说完了，动手算一遍。还是那棵示例树，根是 A。按“根左右”的规则：

第一步，来到根 A，先访问 A。A 记为第 1 个访问的节点。 第二步，进入 A 的左子树，也就是以 B 为根的子树。按照同样的规则，先访问这棵子树的根 B。B 记为第 2 个访问的节点。 第三步，进入 B 的左子树，以 D 为根。D 是叶子，访问它，记为第 3 个。D 没有孩子，D 这棵子树完成。 第四步，回到 B，进入 B 的右子树，以 E 为根。先访问 E，记为第 4 个。E 有左孩子 G，于是进入以 G 为根的子树。 第五步，G 是叶子，访问它，记为第 5 个。G 这棵子树完成，E 的右子树为空，E 的子树完成，B 的子树完成。 第六步，回到 A，进入 A 的右子树，以 C 为根。先访问 C，记为第 6 个。C 没有左孩子，直接进入右子树 F。 第七步，F 是叶子，访问它，记为第 7 个。整棵树遍历结束。

所以前序遍历的完整结果是：A、B、D、E、G、C、F。下面这张图把每个节点的访问序号直接标在节点上，序号 1 到 7 严格对应上面的七步，你可以顺着序号把整个遍历过程“重走”一遍：

有没有发现一个有趣的规律？前序遍历的结果里，任何一个祖先都排在它所有后代的前面。A 在 B、C 前面，B 在 D、E、G 前面，E 在 G 前面。这不是巧合，而是”根左右”规则的必然结果：因为先访问根，再进入子树，所以根永远比子树里的任何节点先被访问。反过来，兄弟之间的先后顺序则由”左子树先于右子树”保证：B 整棵子树走完之后才轮到 C。这两个规律合在一起，就是你以后检查前序遍历结果对不对的”验算器”。

3.3 递归代码

“根左右”翻译成代码，几乎是逐字翻译。用 TypeScript 写，先定义一个二叉树节点的类型，然后写遍历函数：

// 链式存储的二叉树节点
type TreeNode = {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
};

// 前序遍历：返回按访问顺序排列的节点值数组
function preorderTraversal(root: TreeNode | null): number[] {
  const result: number[] = [];

  function dfs(node: TreeNode | null): void {
    if (node === null) return;   // 空树：无事可做，直接返回
    result.push(node.val);       // 1. 访问根
    dfs(node.left);              // 2. 递归遍历左子树
    dfs(node.right);             // 3. 递归遍历右子树
  }

  dfs(root);
  return result;
}

这段代码只有三行是“干活”的，顺序和口诀一字不差：先 push 根的值，再递归左，再递归右。可能有人会问：为什么要嵌套一个 dfs 函数，而不是直接让 preorderTraversal 递归自己？两种写法都可以。嵌套函数的好处是 result 数组只需要创建一次，递归过程中所有调用共享同一个数组，不会因为每次递归都 new 一个新数组而把结果弄丢；如果直接递归，就必须把 result 当作参数一路传下去，或者每次递归返回一个数组合并。嵌套写法在遍历类算法里最省心，所以本篇统一采用这种风格。

再看递归的终止条件：if (node === null) return。这是整个函数唯一会“停下来”的地方。想象递归往下走：preorderTraversal 处理根 A，push 之后调用 dfs(B)；dfs(B) push 之后调用 dfs(D)；dfs(D) push 之后调用 dfs(null) 和 dfs(null)——D 没有孩子，所以两次调用都立刻返回；然后 dfs(D) 结束，回到 dfs(B)，继续 dfs(E)……整条递归链就是靠着“遇到空节点就返回”这个终止条件一层层收尾的。如果没有这个条件，递归就会无限调用 dfs(null)、dfs(null.left)、dfs(null.left.left)……直到把调用栈撑爆，程序报栈溢出（stack overflow）错误。所以请记住：递归函数的终止条件，就是它的生命线。

3.4 前序的直觉：先碰到的先处理

前序遍历还有一个非常直观的解读：它是“到达即访问”。想象你拿着一支笔，从根出发在树上走，每到一个新节点，立刻在纸上记下它的名字，然后再往孩子走。因为你是“到了就记”，所以树的形状越“靠左”，越深的地方会越早被记下；而最右侧的节点往往要等左边一大片都记完才会轮到。这个直觉在后面的迭代写法里会变成一句很实用的话：前序迭代只需要一个栈，弹出谁就访问谁，然后把它的右孩子、左孩子依次压栈，就能得到完全一致的结果。

前序遍历在现实里干什么用？最典型的是复制一棵树：新建一个节点，复制根的值，再递归复制它的左子树和右子树。因为根必须在孩子之前创建（孩子要挂到根下面），所以复制树天然是前序的。还有序列化：把树写进字符串时，如果按照前序顺序写，配合空节点的标记，就能完整记录树的形状，后面反序列化时再按前序顺序重建。这些应用在第 10 章会展开，这里先记住结论：前序是“先建自己，再造孩子”的顺序。

为了确认你真的理解了，再给你一棵更小的树练手：根是 X，X 只有右孩子 Y，Y 只有左孩子 Z。按“根左右”算，前序结果是 X、Y、Z。注意 X 没有左孩子，所以访问完 X 后直接进入右子树；Y 也没有左孩子，所以访问完 Y 后直接进入 Z。看似简单，但很多初学者会把 X 的左孩子当成“空操作”而漏掉 Y 和 Z 之间正确的相对顺序——前序不要求“左子树存在”，它只要求“如果有左子树，必须先于右子树”。空子树直接跳过，仅此而已。

3.5 边界情况演练：空树、单节点与缺边树

三种遍历的递归代码都只有两处边界：空节点返回、非空节点继续。把这两个边界玩熟，边界情况就再也不会吓到你了。先看空树：root 是 null，递归函数一进来就命中 if (node === null) return，结果数组保持为空，三种遍历返回的都是空数组 []。这个行为符合直觉：没有节点可访问，遍历结果自然为空。值得注意的是，代码里“返回空数组”不是特判出来的，而是递归终止条件顺其自然的结果——这提醒我们，写遍历代码时，把空节点处理写对，空树、缺左、缺右、全缺这些情况会一起自动正确。

再看单节点树：只有根 X，没有孩子。前序遍历：访问 X，左右子树都为空，结束，结果是 [X]。中序遍历：左子树为空，访问 X，右子树为空，结果也是 [X]。后序遍历：左右都为空，访问 X，结果还是 [X]。三种遍历在单节点树上结果相同，因为“根的位置”无从挪动——只有一个节点时，无论第几次经过它，访问的都只能是它。这从另一个角度验证了“根的位置决定名字”：名字的差异只有在存在子树时才会显现。

最后看刚才那棵“缺边树”：X 只有右孩子 Y，Y 只有左孩子 Z。前序结果是 X、Y、Z；中序结果是 X、Z、Y；后序结果是 Z、Y、X。请特别注意中序：X 的左子树为空，所以 X 居然是中序的第一个节点，而不是“中间”的节点。这说明“中序”的“中”不是指根在结果序列的正中间，而是指根在“左子树和右子树之间”——当左子树为空时，这个“之间”就退到了最前面。类似的，当右子树为空时，中序的根会出现在最后。很多同学看到中序里根没在中间就怀疑自己算错了，其实不是算错，而是忘了“空子树不计入序列”这个前提。后序里根 X 在最后，因为整棵树都是 X 的“右子树 + 自己”，左右都处理完才能轮到 X，这个结论与直觉一致。

边界情况小结成一句话：空子树不产生任何输出，但它是决定“根在第几个”的隐形参与者。手算时，建议你每到一个节点都先把“左空、右空、都空、都不空”四种子情况过一遍，再写下访问顺序，正确率会高很多。

4 中序遍历：左 → 根 → 右

4.1 定义与口诀

中序遍历的规则是：先遍历左子树，再访问根节点，最后遍历右子树。口诀三个字——“左根右”。和前序对比，唯一的区别就是“根”从最前面挪到了中间：前序是“根左右”，中序是“左根右”。可别小看这一个位置的挪动，它让中序遍历拥有了三种遍历中最特别的性质——对二叉搜索树，中序遍历的结果恰好是从小到大有序的。这个性质是二叉搜索树一切高级操作的基石，后面讲到 BST 时会反复用到。

“左根右”还有一层含义：根节点被访问的时刻，被夹在“左子树走完”和“右子树开始”之间。也就是说，当你在中序遍历中访问某个节点时，它的整棵左子树都已经被访问完了，而它的右子树还一个都没碰。记住这句话，它在后面理解“中序为什么能排序”和“中序迭代为什么要在弹出时访问”时都非常有用。

4.2 为什么对二叉搜索树，中序就是从小到大

先复习一下二叉搜索树（Binary Search Tree，BST）的定义：一棵二叉树，如果对每个节点都满足——左子树里所有节点的值都小于该节点的值，右子树里所有节点的值都大于该节点的值，而且左右子树本身也是二叉搜索树——那么它就是一棵 BST。注意这里说的是“所有节点”，不是“左孩子和右孩子”。比如根是 50，它的左子树里可能有 48，也可能有 3，只要是 50 左边的后代，都必须小于 50。

现在把中序规则“左根右”和 BST 的性质叠在一起看：要遍历一棵 BST 的根节点，我们先是完整走完左子树，然后访问根，再完整走完右子树。而左子树里所有的值都小于根，右子树里所有的值都大于根，于是“左子树全部、根、右子树全部”这个访问顺序，天然就是“小、中、大”。再往深处看，左子树内部又递归地满足同样的性质：左子树的左子树全部小于左子树的根，左子树的根小于左子树的右子树全部……这个“小于关系”一层层套下去，最终整个中序遍历序列必然是严格递增的。数学上可以用归纳法严格证明，但直观上你已经看到了：中序把“左小右大”的树形关系，翻译成了“从小到大”的线性顺序。

下面这棵 BST 是很多教材的经典例子：根 50，左孩子 30、右孩子 70，30 的左孩子 20、右孩子 40，70 的左孩子 60、右孩子 80：

中序遍历它会得到：20、30、40、50、60、70、80。看，正好是一串从小到大排列的数字：

这个性质来自 BST 的不等式：任意节点的左子树全部小于它、右子树全部大于它，所以”左 → 根 → 右”的访问顺序恰好把整棵树按值排序。

这个性质给了我们一个强大的”免费能力”：把 BST 中序遍历的结果写出来，就是所有元素的有序排列。于是”给 BST 排序”只需要一次 O(n) 的遍历；反过来，如果有一串有序数据，也可以构造出 BST 来组织成树形。中序遍历像一座桥，连接着”树形结构”和”线性有序序列”两个世界。许多算法（比如判断一棵二叉树是不是 BST、找出 BST 的第 k 小元素）都会暗中借用这座桥。

4.3 手算例子：还是那棵示例树

现在回到示例树，用“左根右”重新走一遍。这次不能像前序那样“到了就访问”，而要先钻进左子树，等左子树全部结束，才轮到根。

第一步，从根 A 出发。先不访问 A，进入 A 的左子树（以 B 为根）。到了 B，还是先不访问，进入 B 的左子树（以 D 为根）。D 是叶子，它的左子树为空、右子树为空，于是“左根右”只剩下“根”可以执行——访问 D。D 记为第 1 个。 第二步，D 的子树结束，回到 B。此刻 B 的左子树已经走完，轮到访问 B。B 记为第 2 个。 第三步，进入 B 的右子树（以 E 为根）。先不访问 E，进入 E 的左子树（以 G 为根）。G 是叶子，访问 G，记为第 3 个。 第四步，回到 E，E 的左子树走完，访问 E。E 记为第 4 个。E 没有右子树，E 结束，B 结束，A 的左子树结束。 第五步，回到 A，访问 A。A 记为第 5 个。 第六步，进入 A 的右子树（以 C 为根）。先不访问 C，进入 C 的左子树——空的，直接跳过。于是 C 的“左”部分结束，访问 C。C 记为第 6 个。 第七步，进入 C 的右子树（以 F 为根）。F 是叶子，访问 F，记为第 7 个。整棵树遍历结束。

中序遍历的完整结果是：D、B、G、E、A、C、F。把访问序号标在树上：

对比前序的序号（A 是 1、B 是 2、D 是 3、E 是 4、G 是 5、C 是 6、F 是 7），中序的序号发生了很有意思的变化：A 从第 1 名掉到了第 5 名，因为它在左子树全部走完之后才被访问；而 D 仍然是第 1 名，因为它作为最左的叶子，无论哪种遍历都是第一个被”到达并处理”的。你可以把中序序号看成”把左子树整体打包，插到根前面”的结果。

4.4 递归代码

中序的递归代码和前序几乎一样，唯一的区别是把访问动作从最前面挪到中间：

// 中序遍历：返回按访问顺序排列的节点值数组
function inorderTraversal(root: TreeNode | null): number[] {
  const result: number[] = [];

  function dfs(node: TreeNode | null): void {
    if (node === null) return;   // 空树：直接返回
    dfs(node.left);              // 1. 先遍历左子树
    result.push(node.val);       // 2. 再访问根
    dfs(node.right);             // 3. 最后遍历右子树
  }

  dfs(root);
  return result;
}

三行核心代码的顺序和口诀完全一致：左、根、右。请你特别体会一下 push 这一行“卡在中间”的感觉：当递归执行到 push 时，左子树那一整段递归调用已经全部返回，说明左边已经清空；而右子树的递归还没有开始，说明右边还是处女地。这正是 4.1 节那句话的代码形态：访问发生时，左已完、右未动。

如果你把前序和中序的代码并排放在一起，会发现它们之间的差异小到几乎可以忽略：同样是一个空判断、两个递归调用、一个 push，只是 push 的位置不同。这看起来平淡无奇，但恰恰揭示了遍历算法的本质——三种遍历共享同一副骨架，不同的只是“访问动作发生的时间点”。后面第 6 章的“三次经过”视角，会把这句话从代码层面提升到思想层面。

4.5 中序的直觉：从左子树回来后访问

中序还有一种空间上的直觉：把一棵二叉树“拍扁”到一条水平线上时，中序遍历很像把每个节点按它在水平方向上的位置从左到右扫一遍。对 BST 来说，这个“水平位置”恰好对应值的大小，所以扫出来的就是有序序列。对一般的二叉树，虽然没有“大小”可言，但“左子树全部在根左边、右子树全部在根右边”这个空间关系仍然成立——中序就是从最左边的节点开始，一路“从左往右”把树里所有节点扫完。

中序还有一个对称的小知识：如果把“左根右”镜像成“右根左”，得到的是从大到小的逆序输出。这在面试里偶尔会用到：想要 BST 的降序序列，不需要先升序再反转，直接右根左遍历即可。这个小小的对称性，再一次说明“根的位置决定名字”这个总纲——只要调整根的位置，就能派生出全部家族成员。

5 后序遍历：左 → 右 → 根

5.1 定义与口诀

后序遍历的规则是：先遍历左子树，再遍历右子树，最后访问根节点。口诀三个字——“左右根”。它是三种遍历里最“谦让”的一种：根被放到最后，等两个孩子都处理完了，才轮到自己。前序是“先己后人”，后序是“先人后己”，中序则夹在中间，正好对应了三种不同的访问哲学。

“左右根”意味着什么？意味着当你访问某个节点时，它的左子树和右子树都已经被完整地访问过了。换句话说，后序访问根的时刻，是整个子树彻底结束的时刻。这个“结束时刻”极其珍贵，因为它天然适合表达“先处理完所有细节，再汇总结果”的逻辑。程序员的直觉可以这样培养：凡是某个操作需要“孩子的结果都拿到手，才能算自己的结果”，就优先想后序遍历。

5.2 为什么常用于“先处理孩子，再处理自己”

有三个最经典的理由，让后序遍历成为“先孩子后自己”的标准姿势。

第一，释放内存。假设我们用 C/C++ 手动管理一棵树的节点，树结束生命周期时要逐个释放。释放一个节点之前，必须先释放它的左右子树，否则先把根 free 掉，就再也找不到孩子了。所以释放整棵树的顺序必须是：释放左子树、释放右子树、释放根——这恰恰就是后序遍历。这个场景也许离日常业务有点远，但它把“为什么后序”讲得最彻底：信息的传递方向决定了访问顺序。孩子的地址由父亲持有，父亲的地址不被孩子持有，因此必须先顺着父亲找到孩子、释放孩子，最后释放父亲。

第二，计算子树规模。如果要统计以某个节点为根的子树一共有多少个节点，最自然的做法是：左子树的节点数加上右子树的节点数，再加上根自己这 1 个。要拿到左子树的节点数，必须先递归左子树；要拿到右子树的节点数，必须先递归右子树；等两边都返回了数字，根才能把结果加起来。这也是后序：先算孩子，再汇总自己。同理，求子树的最大值、最小值、高度、节点和，凡是“结果依赖子树结果”的，清一色都是后序。

第三，表达式求值。表达式树里，叶子是数字，内部节点是运算符；要计算一个内部节点代表的值，必须先知道左右子树的值。比如一个“加”节点，必须先算出左子树是多少、右子树是多少，才能把两个数加起来。所以表达式树求值必须后序。这一条我们在第 10 章会详细展开，并配一棵真正的表达式树来算一遍，这里先埋下伏笔。

对比一下三种遍历的“气质”：前序适合“先创建根，再造孩子”（复制树）；中序适合“按大小顺序输出”（BST 排序）；后序适合“先搞定孩子，再汇总自己”（求值、统计、释放）。把这三个场景和三种顺序对应起来，以后再遇到新问题，第一反应就不会是“用哪种遍历”，而是“我需要孩子的结果吗”——需要，就后序；只需要按顺序处理，就前序或中序。

5.3 手算例子：把示例树最后走一遍

还是那棵示例树，这次用“左右根”。请做好心理准备：后序是三种遍历里最容易手算出错的一种，因为根被拖到最后，而树的嵌套又深，很容易“走着走着忘了还有谁没访问”。建议你手边拿张纸，边看边画，或者直接在上文示例树那张图上做标记。

第一步，从根 A 出发。A 先不访问，进入左子树 B。B 先不访问，进入 B 的左子树 D。D 是叶子，它的左右子树都为空，于是“左右根”只剩下根，访问 D，记为第 1 个。D 结束。 第二步，回到 B，B 的左子树完成。接着进入 B 的右子树 E。E 先不访问，进入 E 的左子树 G。G 是叶子，访问 G，记为第 2 个。G 结束，E 的右子树为空，E 的左右都完成了，访问 E，记为第 3 个。E 结束，B 的右子树完成。 第三步，B 的左右子树都完成了，访问 B，记为第 4 个。B 结束，A 的左子树完成。 第四步，回到 A，进入右子树 C。C 先不访问，它的左子树为空，直接进入右子树 F。F 是叶子，访问 F，记为第 5 个。F 结束，C 的左右都完成了，访问 C，记为第 6 个。C 结束，A 的右子树完成。 第五步，A 的左右子树都完成了，访问 A，记为第 7 个。整棵树遍历结束。

后序遍历的完整结果是：D、G、E、B、F、C、A。注意根 A 排在最后一个——这是后序最显眼的标志。把访问序号标在树上：

对照一下三种遍历在示例树上的结果：

遍历	结果	根 A 的位置
前序	A、B、D、E、G、C、F	第 1 个
中序	D、B、G、E、A、C、F	第 5 个
后序	D、G、E、B、F、C、A	第 7 个

同一棵树，三种走法，三个完全不同的序列，但访问的都是同样 7 个节点。这就是遍历顺序的意义：内容相同，顺序不同，用途不同。这张小表也会在文末的速查表里再次出现，现在先感受一下。

5.4 递归代码

后序的递归代码照例只挪一行：

// 后序遍历：返回按访问顺序排列的节点值数组
function postorderTraversal(root: TreeNode | null): number[] {
  const result: number[] = [];

  function dfs(node: TreeNode | null): void {
    if (node === null) return;   // 空树：直接返回
    dfs(node.left);              // 1. 先遍历左子树
    dfs(node.right);             // 2. 再遍历右子树
    result.push(node.val);       // 3. 最后访问根
  }

  dfs(root);
  return result;
}

和前序相比，push 从第一行挪到了最后一行；和中序相比，push 从中间挪到了最后。至此，三种递归写法你已经全部见过了，它们共享同一副骨架，只靠 push 的位置互相区分。可以毫不夸张地说：如果你能默写出其中一种，另外两种就是移动一行代码的事。

5.5 后序的直觉：子树结束的时刻

后序遍历的访问时刻，是“整棵子树全部结束”的时刻。你可以把每个节点想象成一个小队的小队长：前序是小队长一到就汇报，中序是汇报完左队再汇报，后序是等左右两队都收工了，小队长才做总结陈词。因此，后序的结果天然有“从叶子往根聚拢”的感觉：叶子们先出现，根最后出现，中间是逐层往上汇总的中间节点。

这种“聚拢感”还有一个实际用途：如果你需要从下往上修改树——比如给每个节点重新计算一个值，而这个值依赖子树的新值——后序遍历可以让你在单次遍历里完成，不需要先遍历一遍收集信息、再遍历一遍回写。很多树形动态规划问题（树形 DP）就是后序的忠实用户：每个节点从孩子那里收集结果，算出自己的结果，再把它传给父亲。等到学树形 DP 时，你会感谢今天花时间把后序想透彻了。

6 三种遍历的关系与记忆方法

6.1 根的位置决定名字

现在三种遍历都见过了，是时候把它们放进同一张图里看。三种遍历的名字——前序、中序、后序——里的“序”，指的不是别的，正是根节点在三段访问里排第几位。把一次完整的遍历抽象成三段：“左子树”、“根”、“右子树”，那么：

• 前序 = 根 + 左 + 右，根在最前，所以叫“前”；
• 中序 = 左 + 根 + 右，根在中间，所以叫“中”；
• 后序 = 左 + 右 + 根，根在最后，所以叫“后”。

这就是全篇最重要的那句口诀：“根的位置决定名字”。以后看到“中序遍历”，不要背“左根右”，而是想“根在中间”；看到“后序遍历”，不要背“左右根”，而是想“根在最后”。口诀“根左右、左根右、左右根”当然也要会，但理解根的位置之后，三句口诀不再需要分别记忆——它们只是一个概念的三次简单挪位。更妙的是，如果你不小心忘了某个口诀，只要回忆“名字里的‘前中后’对应根在第几个位置”，就能立刻把顺序重新推出来。

6.2 统一视角：每个节点都被经过三次

为什么“根的位置”可以这样自由挪动？因为深度优先遍历在物理上有一个统一的行走过程：从根出发，每一个节点都会被“经过”三次——第一次是刚到达它时；第二次是走完它的左子树、回到它准备去右子树时；第三次是走完它的右子树、准备回到父亲时。三种遍历的区别，仅仅在于选择“第几次经过时”进行访问。

拿示例树的根 A 来说：整趟遍历中，你第一次到达 A（前序的访问点），然后钻进 B 的子树；B、D、E、G 全部处理完后，你回到 A，这是第二次经过 A（中序的访问点）；接着钻进 C 的子树；C、F 处理完后，你再次回到 A，这是第三次经过 A（后序的访问点），然后离开整棵树。所以 A 虽然只被“正式访问”一次（具体是哪一次由遍历类型决定），但它作为路径上的必经之点，其实被经过了三次。下面的图把这三个时间点连成了完整的时间线：

这张图是整个深度优先遍历的”心法总图”。你可以把任何一个节点代入 X：对叶子节点，它的左右子树都是空，所以”走完左子树”和”走完右子树”都是瞬间完成，三次经过几乎叠在一起，但概念上依然是三次——第一次经过、空左子树回来、空右子树回来。对根节点，第三次经过之后整棵树结束。理解了”三次经过”，你就同时理解了三种遍历为什么共享同一个递归骨架：骨架是同一个行走过程，只是访问动作被安排在第一次、第二次还是第三次。

6.3 三种遍历一览

把三种遍历放在同一张表里对照，结论一目了然：

遍历	顺序	口诀	访问时刻	访问 A 的序号（示例树）
前序	根 → 左 → 右	根左右	第一次经过	1
中序	左 → 根 → 右	左根右	第二次经过	5
后序	左 → 右 → 根	左右根	第三次经过	7

这张表值得你花 30 秒从头到尾默读一遍，然后合上文章，自己把示例树的前序、中序、后序结果各写一遍。写对之后，你就算真正“拥有”了三种遍历，而不是“见过”它们。

6.4 记忆与验算的实用技巧

最后分享两个实战技巧。第一个技巧：用“最左叶子”和“根”做验算锚点。无论哪种遍历，最左的叶子（一路向左走到头的节点）总是最早被处理的几个节点之一；而根在前序是第 1 个、在中序是左子树个数加 1、在后序是最后一个。手算完一遍后，先检查根的位置对不对，再检查最左叶子在不在开头附近，能快速抓出大部分错误。第二个技巧：用“括号展开”理解嵌套。把一棵子树想象成一对括号，前序是“先写根，再展开左右括号”，中序是“左括号里写左子树，然后写根，再右括号”，后序是“括号里全部写完后，把根写在括号外面”。括号的层数就是递归的层数，压不压栈、什么时候压栈，都和括号配对同构。

6.5 用“三次经过”重看示例树的节点

为了把“三次经过”这个抽象视角变成肌肉记忆，我们挑示例树里两个典型节点，把它们的完整旅程各走一遍。先看叶子 G。整趟遍历中，G 一共被经过三次：第一次，是 E 进入左子树、刚到达 G 的那一刻，前序遍历在这个瞬间访问 G，所以 G 在前序结果里排第 5；第二次，是 G 的左子树（空树）走完、控制权回到 G 的那一刻，中序遍历在这个瞬间访问 G，G 在中序结果里排第 3；第三次，是 G 的右子树（也是空树）走完、准备返回 E 的那一刻，后序遍历在这个瞬间访问 G，G 在后序结果里排第 2。叶子节点的三次经过几乎连续发生，中间只隔着两次“空子树的瞬间完成”，所以叶子在三种遍历里的序号往往挨得很近——G 是第 5、第 3、第 2，确实挤在一块。

再看中间节点 B。B 的旅程要长得多：第一次经过 B，是 A 进入左子树的那一刻，前序在这里访问 B，B 排第 2；然后 B 走进左子树 D，D 结束后回到 B，这是第二次经过 B，中序在这里访问 B，B 在中序里也排第 2（因为 D 先于 B 被访问，而 B 又是 A 的左子树里第一个“非最左”节点）；随后 B 走进右子树 E，E 和 G 全部处理完，再一次回到 B，这是第三次经过 B，后序在这里访问 B，B 在后序里排第 4。你看，同一个 B，因为访问时刻不同，在三个结果里的位置也不同——前序和中序都是第 2，后序却掉到第 4，因为它必须等 E、G 两个“晚辈”全部结束后才轮到自己。

把 B 和 G 的三次经过整理成一张对照表：

节点	第一次经过（前序）	第二次经过（中序）	第三次经过（后序）
B	第 2 个访问	第 2 个访问	第 4 个访问
G	第 5 个访问	第 3 个访问	第 2 个访问

这张表透露了一个更深层的规律：“第几次经过”是物理事实，“访问序号”是访问时刻的投影。三次经过对每个节点都成立，与遍历类型无关；遍历类型只决定把“正式访问”这一件事安插在哪一次经过上。正因为如此，三种遍历才能共享同一个递归骨架——它们走的路径一模一样，只是“打卡”的时机不同。下次你手算到一半犯迷糊时，不要盯着结果序列发呆，回到“三次经过”这张时间线图上，找到当前节点在第几次，一切都会豁然开朗。

7 递归本质：函数调用栈展开过程

7.1 递归函数是怎么“记得”路的

前面三份递归代码，每一份都只有几行，看起来轻飘飘的。但轻飘飘的代码背后，运行着的是一台精密的机器——函数调用栈（call stack）。要真正理解递归，尤其是理解“为什么递归能记住回头路”，必须把这台机器拆开看。好消息是，这台机器的所有零件我们都已经见过了：它就是第 8 章迭代写法里那个显式栈的“亲兄弟”。

先回忆一个基本事实：计算机执行函数时，每调用一个函数，就会在内存里开辟一块区域，叫作栈帧（stack frame）。栈帧里保存着这次调用需要的全部“现场”：函数的参数、局部变量，以及最重要的——返回地址，也就是“这个函数执行完后，该回到哪一行继续”。函数返回时，这块栈帧被销毁，控制权交回给调用者。函数调用可以嵌套：main 调用 f，f 调用 g，那么栈里就有三个栈帧叠在一起，最上面的是正在执行的 g。这个“后进先出”的叠法，正是栈这个数据结构的名字来源。

递归的特殊之处在于：函数调用的还是它自己，但每次调用都是一次全新的调用，拥有自己独立的栈帧。preorder(A) 调用 preorder(B)，这两个虽然同名，却是两个互不干扰的栈帧：A 那一帧记得“我访问完 A 了，等左子树结束，我还要去访问右子树”，B 那一帧记得“我访问完 B 了，接下来要进左子树”。正是这些彼此独立的栈帧，把“走到哪了”“接下来要干嘛”保存得清清楚楚。

7.2 一个具体例子：前序在示例树最左分支上的展开

空谈不如实证。我们用前序遍历跟踪示例树最左的那条分支：A → B → D。忽略 D 之后的右半部分，只看这几次调用如何一层层压栈、再一层层弹栈：

同一时刻，栈里的状态长这样（画到访问 D 为止，最上面是当前正在执行的函数）：

注意栈的”厚度”：它永远等于当前正在走的那条路径的长度。走到 D 时，栈里躺着 A、B、D 三层；从 D 返回到 B 时，D 那一层被弹出，栈变回两层。这个厚度不是巧合——深度优先遍历的本质，就是始终只维护从根到当前节点这一条路径。你不需要记住已经走完的分支，因为那些分支不会再回来了；你只需要记住当前这条”回头路”，以及路上每个节点”接下来还差哪一步没做”。这正是递归”记住回头路”的机制：栈帧就是回头路的路标。

7.3 为什么“返回”能回到正确的位置

还有一个细节值得展开：从 D 返回后，为什么程序知道该去访问 E，而不是重新访问 B？答案是返回地址。preorder(B) 的栈帧里，不仅保存了 B 的指针，还保存了“我刚执行完 dfs(node.left) 这一行，下一行是 dfs(node.right)”。当 preorder(D) 返回时，控制权交回 preorder(B) 的栈帧，程序从保存好的下一行继续执行，于是正确地进入 E。如果 B 帧里没有这个信息，程序就会“失忆”，不知道左子树已经走完。所谓递归“记住回头路”，在机器层面就是这么朴素：每个栈帧把“我在哪、我接下来该干什么”写在身上，返回时照着继续。

这个机制对中序和后序同样成立，只是“访问”这一动作被安排在返回的不同时机：中序的 result.push(node.val) 位于“左递归返回后、右递归开始前”，后序的位于“右递归返回后”。你甚至可以把三种遍历看成同一个栈机，只是“在哪一行做访问”这个设置不同——第 8 章的迭代写法，就是把这台栈机从“隐式”变成“显式”。

7.4 递归的代价与风险

递归优雅，但并非没有代价。每层递归都要创建一个栈帧，栈帧要占内存；深度越深，栈越高，占用越多。当树特别深时（比如一棵退化成链的树，深度等于节点数 n），递归的栈高度会达到 O(n)，如果 n 很大，可能触发编程语言或操作系统的栈溢出限制，程序直接崩溃。这就是为什么工程上有时需要迭代写法：显式栈放在堆内存里，容量比函数调用栈宽松得多，还能精确控制。不过，在绝大多数教学和面试场景里，递归写法的清晰度远胜于它的风险，优先使用递归、在真正需要时才改迭代，是更实用的策略。下一篇讲广度优先时你会看到，BFS 因为要“分层平推”，递归反而不好写，那又是另一番风景。

8 迭代实现：用显式栈模拟递归

8.1 为什么要研究迭代写法

递归写法的代码只有几行，为什么还要费劲研究迭代写法？至少有三个理由。第一，绕过栈溢出：如 7.4 节所说，递归的深度受函数调用栈容量限制，遇到很深很长的树可能崩溃；迭代写法把栈搬到我们自己的数据结构里，容量大得多，还能按需调整。第二，看清本质：递归把栈藏在运行时的调用机制里，很多初学者只学会了“背代码”，说不清为什么能遍历完；显式栈把每一次压栈、弹栈都摆在明面上，写一遍迭代，胜过读十遍递归。第三，面试与工程都爱考：不少面试官喜欢让候选人“不用递归写一遍中序”，考察的就是对栈机制的理解是否到位。

迭代写法有个总纲，请先记住：显式栈模拟的就是函数调用栈。递归里“调用一个函数”对应“压一个栈帧”，“函数返回”对应“弹一个栈帧”。我们不需要模拟栈帧的全部细节（比如返回地址、局部变量），只需要模拟最关键的信息——接下来还要处理哪些节点。想清楚这一点，三种迭代写法的设计思路就都顺了。

8.2 前序迭代：最好写的一种

前序的规则是“根左右”，访问发生在第一次经过节点时。这给了我们一个绝佳的便利：节点一进栈，马上就能决定它的访问顺序。具体做法是：用栈保存“还没访问的节点”，初始把根压栈；每次循环弹出栈顶节点，立刻访问它，然后先把右孩子压栈、再把左孩子压栈。为什么右先左后？因为栈是后进先出，后压进去的会先弹出来。我们想让左孩子先于右孩子被访问，就必须让右孩子先入栈、左孩子后入栈——左孩子压在右孩子上面，下一次弹出时正好是左孩子。这个“反着压”的小动作，是前序迭代的核心。

// 前序遍历：迭代写法（显式栈）
function preorderIterative(root: TreeNode | null): number[] {
  const result: number[] = [];
  const stack: TreeNode[] = [];
  if (root !== null) stack.push(root);   // 根入栈

  while (stack.length > 0) {
    const node = stack.pop()!;           // 弹出栈顶
    result.push(node.val);               // 立即访问
    if (node.right !== null) stack.push(node.right); // 右孩子先入栈
    if (node.left !== null) stack.push(node.left);   // 左孩子后入栈
  }

  return result;
}

用示例树从头到尾跟踪一遍这个栈。为了读起来方便，栈用从左到右表示“从栈底到栈顶”：

对照访问顺序：A、B、D、E、G、C、F，和递归版本完全一致。留意一个细节：栈里永远存着”还没访问的节点”，而且栈顶就是”下一个该访问谁”。这个性质让前序迭代写起来非常舒服——循环体内不需要任何判断分支，弹出、访问、压孩子，三件事干干净净。可以说，前序是三种遍历里迭代最简单的一种，因为它的访问时机（第一次经过）和栈的弹出时机天然同步。

8.3 中序迭代：要绕一下

中序的麻烦在于：访问不能发生在“第一次遇到节点”时，必须等左子树走完。可栈是后进先出的，你压入一个节点后，无法让“它下面的东西”先出来——除非你换个思路：不要一遇到节点就压栈后马上处理它，而是先一路向左，把整条左链压进栈里。等再也走不动了，栈顶就是“左子树全部为空或全部走完”的那个节点，这时候弹出它并访问，然后把目光转向它的右子树，重复“一路向左”的过程。

// 中序遍历：迭代写法（显式栈）
function inorderIterative(root: TreeNode | null): number[] {
  const result: number[] = [];
  const stack: TreeNode[] = [];
  let cur: TreeNode | null = root;

  while (cur !== null || stack.length > 0) {
    // 1. 一路向左，把所有左链上的节点压栈
    while (cur !== null) {
      stack.push(cur);
      cur = cur.left;
    }
    // 2. 弹出栈顶：此时它的左子树已经全部处理完
    cur = stack.pop()!;
    result.push(cur.val);   // 3. 访问它
    cur = cur.right;        // 4. 转向右子树，下一轮循环处理
  }

  return result;
}

这个写法里有几个容易懵的点，逐个说清。外层 while 的条件是 cur !== null || stack.length > 0：只要还有“待处理的节点”或者“栈里还压着节点”，循环就继续。内层 while 负责“向左走到黑”，它把当前节点以及一路上的所有左孩子压栈。弹出的时机就是访问时机：弹出时，该节点的左子树已经全部结束（因为左子树要么为空，要么早就被递归式地处理完了），这正是中序要求的“左已完、右未动”。最后把 cur 指向右孩子，右子树会在下一轮循环里被同样处理。整个循环，其实是把递归中“先左、再根、后右”的时序，一丝不差地搬到了显式栈上。

用示例树跟踪一遍（同样约定栈从左到右是栈底到栈顶）：

访问顺序 D、B、G、E、A、C、F，与递归中序完全一致。如果你把这段跟踪过程与第 7 章的函数调用栈展开对照，会发现它们是同一台机器：内层”一路向左”对应递归里”先调用左子树”，弹出访问对应”左子树返回后执行 push”，转向右对应”调用右子树”。递归是隐式栈，迭代是显式栈，仅此而已。

8.4 后序迭代：最绕的一种

后序的访问要等两个孩子都处理完，这让“弹出即访问”的策略彻底失效：你弹出节点时，怎么知道它的右子树处理完没有？为此，教材上至少有三类解法：双栈法、反转法、标记法。这里先讲最巧妙的反转法，再提一句标记法作为进阶。

反转法的思路值得玩味：后序是“左、右、根”，如果我们能先得到一个“根、右、左”的序列，再整体反转，不就成了“左、右、根”吗？而“根、右、左”恰恰是前序的镜像——把前序里“先压右再压左”改成“先压左再压右”，访问顺序就会从“根左右”变成“根右左”。于是算法分成两步：第一步，用前序的框架但交换压栈顺序，得到“根右左”的临时序列；第二步，把临时序列整体反转。两步合起来，就是一个简洁的后序迭代。

// 后序遍历：迭代写法（反转法）
function postorderIterative(root: TreeNode | null): number[] {
  const result: number[] = [];
  const stack: TreeNode[] = [];
  if (root !== null) stack.push(root);

  while (stack.length > 0) {
    const node = stack.pop()!;
    result.push(node.val);                    // 先得到“根右左”序列
    if (node.left !== null) stack.push(node.left);  // 注意：与前序相反
    if (node.right !== null) stack.push(node.right);
  }

  return result.reverse();                    // 整体反转成“左右根”
}

跟踪示例树（第一遍得到临时序列，第二遍反转）：

反转法胜在好记、好写，但也有一个微妙的缺点：它需要额外的 O(n) 空间存临时序列（虽然本来就要存结果数组，实际开销通常可接受），而且访问顺序不是”真正意义上”的后序——中间过程里访问是提前发生的。如果面试官问”不借助反转，写出真正的后序迭代”，就需要标记法：每个节点入栈时附带一个状态，第一次弹出表示”左子树还没处理”，第二次弹出表示”右子树还没处理”，第三次才真正访问。实践中常用”当前节点 + 是否已访问右子树”的二元组，或者用一个 prev 指针记录上一个访问的节点。标记法的空间还是 O(h)，逻辑上更贴近递归，这里先点到为止，作为你读完本篇后的进阶练习。

8.5 为什么前序好写，中序和后序要绕一点

把三种迭代写法放在一起看，你会得到一个重要的规律：访问时机越早，迭代越好写。前序在第一次经过节点时就访问，所以“弹出即访问”直接成立，代码最短；中序要等左子树完成，于是必须用“一路向左 + 弹出 + 转向右”的双循环结构，把访问延迟到弹出时刻；后序要等两个孩子都完成，单靠一个栈的弹出时机无法直接表达“第三次经过”，于是要么反转、要么标记，最绕。这个规律在写代码前就能预判：先想清楚“访问发生在第几次经过”，再决定栈里要存什么。存“还没开始的节点”，前序就够了；存“进行到一半的节点”，中序需要额外记录位置；存“连孩子都处理完的节点”，后序就必须加状态。理解了这条主线，迭代写法就不再是三段需要死记的代码，而是一道可以现场推导的推理题。

9 复杂度分析：时间 O(n)，空间 O(h)

9.1 时间复杂度：每个节点被处理固定次数

三种遍历的递归版和迭代版，时间复杂度都是 O(n)，其中 n 是树的节点总数。为什么？因为每个节点都只会被“处理”固定次数：递归版里，每个节点恰好被访问一次，左右各递归一次，一共是常数次操作；迭代版里，每个节点最多入栈一次、出栈一次、访问一次，同样是常数次操作。把 n 个节点的常数倍工作加起来，就是 O(n)。如果你细心，会发现在“三次经过”视角下，每个节点其实被“经过”三次，但那三次加在一起仍然是常数次，3n 还是 O(n)，常数 3 不影响量级。所以无论树长得多么歪、多么深，三种遍历的时间都是线性的——访问整棵树，至少要花“看一遍所有节点”的时间，而线性时间正好是最优的。

时间复杂度里还有一个隐藏的细节：递归版每次函数调用的开销（压栈、弹栈、跳转）比迭代版的循环体略大，所以常数上递归稍慢；但如果只比较数量级，两者完全一样，都是 O(n)。在算法分析的语境里，O(n) 就是结论，不需要为常数差焦虑。真正需要区分递归与迭代的，是下面要讲的空间复杂度。

9.2 空间复杂度：栈的高度等于树的深度

空间复杂度要分两种实现分别看，但它们殊途同归。递归版的空间，是函数调用栈的最大深度，也就是递归最深时栈里有多少帧。最深时你正走在从根到某个叶子的一条路径上，栈里的帧数正好等于这条路径的长度，也就是树的深度。迭代版的空间，是显式栈的最大长度：前序迭代栈里压着“还没访问的节点”，栈的高度同样不超过树的深度；中序迭代栈里压着左链上的节点，高度也是当前路径长度；后序反转法的临时序列虽然要 O(n)，但如果按“真后序”的标记法写，栈高同样是 O(h)。因此，三种遍历的空间复杂度统一写作 O(h)，其中 h 是树的高度（深度）。这里的 h 不是节点数 n，而是一条从根到叶子的最长路径上的节点数（按边数算则差一个常数）。

O(h) 意味着什么？它意味着遍历一棵树所需的额外内存，和树有多“高”有关，而和树有多“宽”无关。同一棵 7 节点的示例树，无论把它画得多么矮胖，h 都不变，空间需求也不变。这个结论和下一篇的广度优先遍历形成鲜明对照：BFS 用队列逐层扫描，空间是 O(w)，w 是树的最大宽度。一高一宽，正好是深度优先与广度优先在资源消耗上最本质的分野。

9.3 最坏情况与最好情况

树的高度 h 不是固定的，它取决于树的形状，所以 O(h) 这个式子在不同形状下会“伸缩”。最好情况：树接近平衡（比如满二叉树），节点数 n 和高度 h 满足 h = O(log n)，空间复杂度就是 O(log n)。n 等于 100 万时，log n 大约只有 20，递归栈只有二十来层，非常轻松。最坏情况：树退化成一条链——每个节点最多只有一个孩子，比如“右右右……右”的斜树——此时 h = n，空间复杂度变成 O(n)。n 等于 100 万时，栈可能高达 100 万层，递归版几乎必然栈溢出，这也是 7.4 节提醒过的问题。平均情况：对随机生成的二叉树，树高大约在 O(√n) 到 O(log n) 之间，具体分布取决于生成模型，面试里通常不需要精确计算，记住“平衡树 O(log n)，链状树 O(n)”就够用了。

把结论整理成表：

树的形状	高度 h	遍历空间	典型例子
满二叉树 / 近似平衡	O(log n)	O(log n)	大多数“健康”的 BST
一般形态	介于 log n 与 n 之间	O(h)	随机树
链状（斜树）	O(n)	O(n)	一直只有右孩子的树

时间方面三种形状都是 O(n)，无需再分。最后给你一个判断题检验理解：一棵有 1000 个节点的完全二叉树，递归中序遍历最多同时存在多少层栈帧？答案是约 10 层（log 以 2 为底 1000 约等于 10）。如果题目把这棵树换成 1000 个节点连成一条直线，答案就变成约 1000 层。同样遍历 1000 个节点，内存需求相差百倍，这就是“形状决定复杂度”的生动写照。

9.4 递归还是迭代？一个实用的决策流程

既然递归和迭代都能完成遍历，到底该用哪个？我的建议是分三步决策。第一步，默认递归：递归代码只有几行，和“根左右、左根右、左右根”的口诀一一对应，正确性最容易确认，也最容易向别人解释。写算法题、做学习验证、维护小规模数据，递归都是首选。第二步，评估树的深度：如果树可能很深（比如上百万个节点的链状树，或者数据来自用户输入、你无法控制形状），就要提前算一笔账——递归栈深 O(h)，h 接近 n 时风险陡增。第三步，必要时切换迭代：当深度风险真实存在，或者运行环境对调用栈限制苛刻（比如嵌入式、某些脚本引擎、高并发服务），再换成显式栈的迭代写法。切换时优先选好写的前序与中序迭代，后序则根据需求在反转法与标记法之间取舍。

还有一个常见的误解值得澄清：树的遍历无法写成“尾递归”。尾递归是指函数的最后一个动作就是调用自身，编译器可以优化成循环、不增长栈；但树的深度优先遍历在每个节点最多有两个递归调用，而且调用之后还要继续处理另一半子树，天然不是尾递归。所以不要指望“加个尾递归优化”就能让树的递归遍历免于栈溢出。真正解决问题的办法，要么是显式栈迭代，要么是先把树变平衡（很多自平衡树存在的意义之一，就是保证深度始终是 O(log n)，让递归遍历永远安全）。这也是为什么工程界一边用递归写树算法，一边又对“树高”这件事极其敏感——深度不是树的装饰品，它直接决定算法能不能跑起来。

10 应用：遍历不是目的，是手段

遍历本身很少是最终目标——打印一遍、数一遍节点，只是练习题。真正的价值在于，几乎每个树算法都以某种遍历为骨架。这一章挑四个代表性应用，让你看看前序、中序、后序分别在真实问题里扮演什么角色。

10.1 表达式树求值：后序的经典舞台

表达式树把数学表达式变成一棵二叉树：叶子是数字，内部节点是运算符，左右子树是运算的两个操作数。下面这棵树表示 (2 + 3) × (5 - 1)：

要求这棵树的值，必须后序遍历：先算左子树 2 + 3 = 5，再算右子树 5 - 1 = 4，最后算根 5 × 4 = 20。用前序或中序行不行？不行。前序先访问根”ד，可这时左右子树的值还没算出来，拿什么相乘？中序先访问左子树再访问根，左子树算完了，右子树却还没开始，根还是凑不齐两个操作数。只有后序能保证”访问根时，两个孩子已经算完”。这个例子把 5.2 节”先处理孩子，再处理自己”讲得再直白不过了。

代码几乎是后序遍历的套壳：

type ExprNode = {
  isNumber: boolean;
  value?: number;
  op?: string;
  left: ExprNode | null;
  right: ExprNode | null;
};

function evaluate(root: ExprNode | null): number {
  if (root === null) return 0;
  if (root.isNumber) return root.value!;      // 叶子：直接返回值
  const left = evaluate(root.left);           // 先算左孩子
  const right = evaluate(root.right);         // 再算右孩子
  switch (root.op) {                          // 最后做运算
    case '+': return left + right;
    case '-': return left - right;
    case '*': return left * right;
    case '/': return right === 0 ? NaN : left / right;
    default: return NaN;
  }
}

顺带一提，如果你把后序遍历的节点值直接写出来，会得到 2 3 + 5 1 − ×——这正是逆波兰表达式（后缀表达式）。计算机用栈求逆波兰表达式时，遇到数字压栈、遇到运算符弹出两个数计算再压回，本质上和表达式树的后序求值是同一件事，只是树形结构被拍平成序列。所以学会后序遍历，等于同时理解了计算器、编译器和解释器里常见的一整套机制。

10.2 复制树：前序的看家本领

复制一棵二叉树，要用前序。理由在 3.4 节提过：必须先创建根节点，才能把左子树、右子树的副本挂到它下面。如果先复制左子树，复制完才发现没有“根”可以挂，就会手足无措。前序“先建自己，再造孩子”的顺序，完美匹配“父引用子”的存储结构：

function cloneTree(node: TreeNode | null): TreeNode | null {
  if (node === null) return null;                 // 空节点：复制为空
  const copy: TreeNode = { val: node.val, left: null, right: null };
  copy.left = cloneTree(node.left);               // 递归复制左子树
  copy.right = cloneTree(node.right);             // 递归复制右子树
  return copy;
}

这段代码严格遵循“根、左、右”的顺序：先 new 出 copy，再填充左右孩子。执行完后，你得到一棵全新的树，新树和旧树结构完全相同，但所有节点都是新建的，修改新树不会影响旧树——这就是“深拷贝”。如果面试里问“如何深拷贝一棵树”，答案就是这段前序递归。注意，这里虽然访问（创建）发生在递归之前，但递归骨架和后序求值完全一样：同一个骨架，换一下“做什么”和“什么时候做”，就变成完全不同的算法。这再次印证了遍历作为“万能骨架”的地位。

10.3 序列化与反序列化：先预告，细节留给后面

“序列化”是把内存里的树转成字符串（或字节流）保存下来，“反序列化”是再把它还原成树。遍历在其中扮演什么角色？关键在于：只要规定好遍历顺序和空节点的表示，一棵树就可以被唯一地写成线性序列。最常用的方案就是前序：遇到节点写它的值，遇到空节点写一个特殊标记（比如 #），遍历完得到一串用逗号分隔的字符串：

function serialize(root: TreeNode | null): string {
  const parts: string[] = [];
  function dfs(node: TreeNode | null): void {
    if (node === null) {
      parts.push('#');
      return;
    }
    parts.push(String(node.val));   // 前序：先写自己
    dfs(node.left);                 // 再写左子树
    dfs(node.right);                // 最后写右子树
  }
  dfs(root);
  return parts.join(',');
}

为什么前序序列化能唯一还原树？因为“值 + 空标记”的序列里，空标记充当了“到此为止”的哨兵，反序列化时按同样的前序顺序消费序列，遇到 # 就返回 null，否则创建节点、递归消费左子树、再消费右子树，整棵树就能被逐步“拼”回来。第 4 篇的预告里说过序列化是存储的延续，本篇则说明序列化就是遍历的产物：没有遍历，树就只能是内存里的临时结构；有了遍历，树才能旅行到文件、网络和另一台机器上。反序列化代码和序列化完全镜像，留作你的课后作业；更完整的讨论（包括为什么中序加前序能重建树、层级序列化等）会在树系列后面的文章里展开。

10.4 目录遍历：日常里随处可见的 DFS

最后一个应用离你最近：文件系统的目录树。一个文件夹里有子文件夹和文件，子文件夹里又有更深的内容，这天然就是一棵多叉树。操作系统的“递归删除文件夹”必须用后序：先删光子文件夹里的文件，再删子文件夹自己，最后才能删最外层文件夹——顺序反了，系统会提示“目录不是空的”。而“打印目录树”则用前序：先打印当前文件夹的名字，再逐层缩进打印它的子项，这样目录树的层次感才能显示出来。用伪代码表示：

function printDirTree(path: string, indent: string): void {
  console.log(indent + path);                // 前序：先输出自己
  for (const child of readDirectory(path)) {
    if (child.isDirectory) {
      printDirTree(child.fullPath, indent + "  ");
    } else {
      console.log(indent + "  " + child.name);
    }
  }
}

这个例子里，树可能是多叉的，但深度优先的思想完全不变：一条分支走到最深的文件，再逐层返回处理下一个子目录。你每天用的文件管理器、打包工具、代码仓库的目录展示，背后都是同一个 DFS。树形结构与人类组织信息的习惯天然契合，而 DFS 是把这种结构“读出来”的默认方式。另外，你在查找实验室里看到的 BST 查找，其实也是一种“定向的 DFS”：每到一个节点比较一次，决定只走左还是只走右，跳过了整棵不相关的子树。理解了这个关系，你会明白为什么二叉搜索树的查找平均只需要 O(log n)——因为每一步都剪掉一半的搜索空间，而这正是“深度优先 + 有序结构”碰撞出的火花。

10.5 更多应用速览：树高、相同性、叶子统计

除了前面四个“大应用”，还有三个小而经典的问题，能帮你把三种遍历的直觉彻底钉牢。

第一个是求树的高度。树高的定义是从根到最远叶子经过的边数（按节点数算则加一），这个值天然是“孩子结果汇总成自己的结果”：左子树的高度、右子树的高度，取较大者再加一，就是当前树的高度。这明显是后序逻辑，代码长这样：

function treeHeight(node: TreeNode | null): number {
  if (node === null) return -1;                        // 空树高度按 -1，根单节点则为 0
  const left = treeHeight(node.left);                  // 先问左子树
  const right = treeHeight(node.right);                // 再问右子树
  return Math.max(left, right) + 1;                    // 汇总 + 1
}

注意这里的约定：空树返回 -1，所以单节点树的高度是 max(-1, -1) + 1 = 0，符合“根到叶子 0 条边”的定义；如果你习惯“层数”定义，把空树返回 0、结果返回 max(left, right) + 1 即可，单节点树就是 1。两种约定都有人用，面试时先说清楚你的约定，比埋头写对更重要。

第二个是判断两棵树是否完全相同。完全相同的定义是：结构相同，且对应节点的值相同。这可以用一次“同步的深度优先”解决：两个节点都为空，说明当前位置相同；一个空一个不空，说明结构不同；值不同，说明内容不同；否则递归比较左孩子、再比较右孩子。顺序上其实同时包含了前序的味道（先比根）和逐层深入的过程，但骨架依然是 DFS：

function isSameTree(p: TreeNode | null, q: TreeNode | null): boolean {
  if (p === null && q === null) return true;           // 都空：相同
  if (p === null || q === null) return false;          // 一个空一个不空：不同
  if (p.val !== q.val) return false;                   // 根值不同：不同
  return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}

第三个是统计叶子节点数量。叶子是没有孩子的节点，判断条件只有一个：left 和 right 都为 null。统计本身不需要特定顺序，但用后序写最顺手——先数左子树有几片叶子，再数右子树有几片，加起来；如果当前节点自己是叶子，就返回 1：

function countLeaves(node: TreeNode | null): number {
  if (node === null) return 0;                         // 空树没有叶子
  if (node.left === null && node.right === null) return 1; // 叶子：算 1 片
  return countLeaves(node.left) + countLeaves(node.right); // 汇总左右
}

这三个小例子加起来告诉你一件事：遍历不是终点，而是算法大厦的脚手架。树高、相同性、叶子统计、求值、复制、序列化、目录管理……表面上千奇百怪，内里全是同一套 DFS 骨架，只是把“访问动作”替换成“计算、比较、创建、输出”而已。以后遇到新的树问题，先问自己三个问题：我需要在什么时候拿到孩子的结果？我需要按什么顺序输出？我的答案依赖子树结果还是只依赖当前节点？三个问题一问，用哪种遍历、递归还是迭代，答案自己就出来了。

11 三种遍历速查表

把本篇全部核心结论压缩进一张表，方便你以后复习时一页看全：

项目	前序遍历	中序遍历	后序遍历
口诀	根左右	左根右	左右根
访问时刻	第一次经过节点	第二次经过节点（左子树结束后）	第三次经过节点（左右子树都结束后）
示例树结果	A、B、D、E、G、C、F	D、B、G、E、A、C、F	D、G、E、B、F、C、A
BST 上的效果	根在前，先于所有后代	从小到大有序	根在最后，叶子先出
典型应用	复制树、序列化	BST 排序与校验	表达式求值、子树统计、释放树
递归代码要点	push 在最前	push 在两次递归中间	push 在最后
迭代写法	弹出即访问，右先左后入栈	一路向左压栈，弹出时访问，转向右	反转法：根右左 + 反转；或标记法
时间 / 空间	O(n) / O(h)	O(n) / O(h)	O(n) / O(h)

再送你一句压箱底的话：三种遍历，一套骨架，三次经过，一根栈。骨架是“先左后右”的递归行走，经过次数是三次，栈是承载这一切的容器，根的位置决定了访问发生在第几次。把这句话想明白，树系列的遍历部分就真正通关了。

12 自测题

下一篇预告：《树系列第 6 篇：广度优先遍历》

深度优先的三兄弟——前序、中序、后序——已经全部登场。但树的遍历故事还没有讲完：还有一种截然不同的走法，它不急着往深处钻，而是从根开始，一层一层、从左到右地扫描整棵树，就像用 X 光给树拍一张“横切面”。这种走法叫广度优先遍历（Breadth-First Traversal），也叫层序遍历。在第 6 篇里，我们会认识它的武器——队列，看它如何做到“先进先出、层层平推”，对比它与深度优先在空间复杂度、搜索习惯上的差异，还会解锁一个深度优先做不到的经典能力：按层处理树。二叉树的层序、锯齿形遍历、求树的最大宽度、找每一层的最值……这些题目都将在第 6 篇逐一登场。我们下一篇见。