企业官网建设流程全解析

很多人学二叉树，最先接触的就是前序、中序、后序遍历这三种遍历方式。“根左右、左根右、左右根”这种口诀背得很熟，可真到了刷题、写工程或者面试手撕代码的时候，反而容易懵：为什么这个场景要用中序？为什么那个场景要用后序？三种遍历的顺序到底怎么来的？

这篇文章就把二叉树的前序、中序、后序遍历一次讲透。不讲虚的，直接围绕三件事展开：三种遍历的本质区分是什么，代码层面递归和迭代分别怎么写，最重要的是——它们各自到底在什么场景下派上用场。我会结合序列化、表达式求值、二叉搜索树处理、树形结构删除等真实例子，把每个遍历的“性格”和“适用场景”说清楚。适合刚学数据结构的学生、准备算法面试的开发者，以及工作中需要手写树形结构处理的工程师。

1. 三种遍历的本质：根节点在什么时候被访问

1.1 从二叉树的结构看遍历顺序

先明确一个基本认知：二叉树由三部分组成——根节点、左子树、右子树。遍历一棵树，本质上就是把这三部分都“过”一遍。而前序、中序、后序这三种遍历方式，唯一的区别就是根节点被访问的时机。

前序遍历，也就是先序遍历：先访问根节点，然后遍历左子树，最后遍历右子树。缩写就是“根左右”。

中序遍历：先遍历左子树，然后访问根节点，最后遍历右子树。缩写是“左根右”。

后序遍历：先遍历左子树，然后遍历右子树，最后访问根节点。缩写是“左右根”。

你看，左子树永远在右子树前面被遍历，这个顺序在三种遍历里是不变的。变得只有一件事：根节点排在第几个。前序根在最前，中序根在中间，后序根在最后。这就是全部的秘密。

1.2 用递归展开的方式理解顺序

有人可能会问：那左右子树内部又是怎么遍历的？答案是——递归地按同样的规则遍历。

举个例子，一棵树结构如下（注意这里不涉及具体数值，只描述结构）：

• 根节点 A
• A 的左子树以 B 为根，B 有一个左孩子 D
• A 的右子树以 C 为根，C 有一个右孩子 E

前序遍历的过程是：先访问 A，然后进入以 B 为根的左子树，在左子树内部又执行“根左右”——访问 B，再访问 D。接着回到 A 的右子树，执行同样的规则：访问 C，再访问 E。最后得到序列 A、B、D、C、E。

中序遍历的过程是：先进入 A 的左子树，在 B 子树内部先访问 D，再访问 B，然后回到 A，访问 A，再进入右子树，访问 C，最后访问 E。得到序列 D、B、A、C、E。

后序遍历的过程是：先进入 A 的左子树，内部先访问 D，再访问 B；然后进入 A 的右子树，先访问 E，再访问 C；最后访问根 A。得到序列 D、B、E、C、A。

理解这个递归展开很重要。很多人背口诀只记住了“根左右”三个字，但真正写递归代码时，不知道“根左右”里的“左”和“右”是递归地执行整套规则，于是代码写得磕磕绊绊。你要是能把一棵三层的树手写出遍历结果，基本就掌握了。

1.3 快速手算验证的一个小技巧

做遍历相关的题目时，有个很实用的快速判断方法：

• 前序遍历结果中，第一个元素一定是整棵树的根节点。
• 后序遍历结果中，最后一个元素一定是整棵树的根节点。
• 中序遍历结果中，根节点在序列的中间位置，并且根节点的左边是左子树的全部节点，右边是右子树的全部节点。

这个规律在反推二叉树、验证遍历结果时非常好用。比如给你一个前序序列和一个中序序列让重建二叉树，核心思路就是先从前序序列中拿到根，再到中序序列中找到根的位置，从而切分左右子树，然后递归处理。

三种遍历的核心对比，用一张表说明：

2. 核心细节解析：递归实现与边界处理

2.1 递归模板：三个函数的写法其实只有一行之差

递归是三种遍历最直观的实现方式，因为二叉树的定义本身是递归的：一棵树的左子树和右子树，依然是二叉树。所以用递归去遍历，代码几乎就是按定义翻译。

以 Python 为例，常规的递归实现大概是这个样子：

class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right def preorder(root): if root is None: return [] res = [] res.append(root.val) # 访问根 res.extend(preorder(root.left)) # 遍历左子树 res.extend(preorder(root.right)) # 遍历右子树 return res def inorder(root): if root is None: return [] res = [] res.extend(inorder(root.left)) # 遍历左子树 res.append(root.val) # 访问根 res.extend(inorder(root.right)) # 遍历右子树 return res def postorder(root): if root is None: return [] res = [] res.extend(postorder(root.left)) # 遍历左子树 res.extend(postorder(root.right)) # 遍历右子树 res.append(root.val) # 访问根 return res

你看，三个函数结构完全一样，只有res.append(root.val)这一行的位置不同：在左右子树递归之前就是前序，在两者之间就是中序，在两者之后就是后序。

递归的终止条件是if root is None: return []。这个细节值得说道说道。很多初学者会写if root.left is None and root.right is None来判叶子节点，其实没有必要。让空子树进入递归，在函数入口直接返回即可，代码更简洁，也不需要为叶子节点单独写分支。

2.2 为什么递归天然契合这三种遍历

递归之所以和二叉树遍历这么搭，是因为二叉树本身就是递归结构的：根节点下挂两个子树，每个子树又是“一个根节点加两个子树”。遍历时，你要处理的是“当前节点 + 两个子任务”，而且两个子任务的结构和父任务完全一致。这种自相似性，让递归成了最自然、最省脑子的写法。

比如说后序遍历，你希望左子树处理完、右子树处理完，最后才轮到根节点。递归写法就是先完整调用左子树的递归函数，再完整调用右子树的递归函数，最后处理根。这个执行顺序是语言层面保证的，只要把代码按“先左后右最后根”的顺序写，就不会错。

很多人在理解递归时的一个误区是：觉得递归是“一层一层压栈再逐层返回”，太抽象。其实换个角度看，递归遍历更像是在执行一个“任务清单”：每个节点都有一个任务清单，上面的内容是“访问根”“访问左子树”“访问右子树”。前序遍历就是按“访问根、访问左子树、访问右子树”的顺序执行清单；执行到“访问左子树”时，把左子树的清单摊开，继续执行。理解到这个层面，三种递归实现基本就通了。

2.3 复杂度与边界：时间 O(N)、空间 O(H)

三种递归遍历的时间复杂度都是 O(N)，其中 N 是节点数。因为每个节点恰好被访问一次，没有重复访问，也没有遗漏。这个复杂度是最优的，你不可能做到比 O(N) 更好——毕竟每个节点都得看一眼。

空间复杂度方面，递归实现的空间消耗来自函数调用栈。最坏情况下树退化成链表（比如只有左子树的斜树），递归深度是 N，空间复杂度是 O(N)。最好情况下，也就是完全二叉树，递归深度是 log N，空间复杂度 O(log N)。所以准确地说，递归空间复杂度是 O(H)，H 是树的高度。这个“H”在极端情况下等于 N，在平衡情况下等于 log N。

这里有个实际提示：当树的规模很大、深度很深时，递归遍历可能触发程序栈溢出（比如 Python 里大量递归默认有一个递归深度限制）。这个问题的应对方法，放在第 5 部分专门讲。

2.4 用 DFS 的“访问时机”统一三种遍历

如果你熟悉深度优先搜索（DFS），可以把三种遍历统一到一个框架里理解。DFS 遍历二叉树时，每个节点会经历三个关键时刻：

• 第一次到达该节点时
• 从左子树返回该节点时
• 从右子树返回该节点时

前序遍历，就是在“第一次到达该节点”时执行访问操作。中序遍历，就是在“从左子树返回该节点”时执行访问操作。后序遍历，就是在“从右子树返回该节点”时执行访问操作。

这个视角非常有价值。它解释了为什么同一个 DFS 过程中，只要改变“输出那行代码的位置”，就能产生三种不同的遍历序列。你也可以基于这个思路，写一个带状态标记的统一遍历模板，这个在后面的迭代实现部分会用到。

3. 实操过程与核心环节实现：手写迭代版本

递归好看但性能有隐患，面试也常要求写出非递归版本。这一部分把三种遍历的迭代写法核心套路讲透，不贴大段代码，重点讲清楚“栈是怎么用的”，因为迭代遍历的本质就是用显式栈模拟递归的函数调用栈。

3.1 迭代前序：先压右子树，再压左子树

前序遍历的迭代写法是最容易理解的。既然遍历顺序是“根左右”，那我们从根节点出发，访问一个节点之后，需要记下接下来还要去访问哪些节点。用栈来存“待访问节点”。

出栈顺序是后进先出。为了让左子树先被访问，右子树后访问，入栈时要先压右子树，再压左子树。流程如下：

• 根节点入栈
• 栈不为空时，弹出栈顶节点，访问它
• 如果该节点有右孩子，右孩子入栈
• 如果该节点有左孩子，左孩子入栈
• 重复直到栈空

弹出顺序就是：先根，再左子树…，最后右子树。这个实现写起来非常短，很多标准库或者算法模板里就是这个写法。

这里容易踩的一个小坑是入栈顺序。新手容易写成“先压左再压右”，结果遍历出来变成“根右左”，和前序遍历正好相反。记住一个生活化类比：栈像一摞盘子，后放上去的先拿走。你希望左子树先被访问，就得把左子树放到栈顶，那就要后压左子树。

3.2 迭代中序：向左走到头，出栈拐向右

中序遍历的迭代写法比前序麻烦一点，核心是“一直往左走，直到走不动，然后出栈访问节点，再转向右子树”。

流程如下：

• 用一个指针 cur 从根节点开始
• 只要 cur 不为空，就入栈，然后 cur = cur.left（一路向左）
• 当 cur 为空时，弹出栈顶节点，访问它
• 然后将 cur 设为弹出节点的右孩子
• 外层循环继续，直到 cur 为空且栈为空

这个写法的关键理解在于：中序是“左根右”，一个节点的左子树没有被完全遍历完之前，这个节点不能出栈。所以用一个栈把沿途的左祖先们全部暂存，等左子树处理完毕，再弹出父节点访问，最后转向右子树。

迭代中序是我个人认为最值得反复手写几遍的遍历，因为它的逻辑不是简单地“按顺序压栈”，而是包含了“沿左链深入、回溯、转右”三个动作，理解了它，很多带状态的树形问题都会好做很多。

3.3 迭代后序：三个主流套路

后序遍历的迭代写法是三种中最麻烦的，因为根节点在最后访问。这意味着你第一次经过根节点时不能访问它，必须等左右子树都处理完再回来访问。迭代时需要额外记录“当前节点是从左子树返回的还是从右子树返回的”。主要有三个主流套路。

第一个套路是双栈法。核心思想是：用第一个栈按“根、右、左”的顺序压入节点，弹出后放入第二个栈，最后第二个栈弹出的顺序就变成“左、右、根”。这个思路巧妙但多用一个栈，理解起来有点绕。

第二个套路是prev 指针法。用变量 prev 记录“上一次访问的节点”。当栈顶节点出栈时，如果node.right is None or node.right == prev，说明右子树已经处理完，可以访问当前节点；否则先把右子树压栈。这里的判断逻辑核心是“确保左右子树都访问完了才访问根”。

第三个套路是状态标记法。直接在栈里存“节点 + 是否已访问”的标记。第一次出栈时发现没访问过，把“根节点重新标记为已访问”重新入栈，再把右子节点和左子节点依次入栈；如果弹出时发现已访问，就直接输出节点值。这个写法最不容易出错，因为它把“什么时候访问根”的决定权交给了标记位，代码逻辑最接近递归语义。

实际面试中，如果你对双栈法不熟，用状态标记法也完全没问题，写出正确代码永远是第一位的。

3.4 Morris 遍历提一句

Morris 遍历是基于线索二叉树思想实现的 O(1) 空间遍历方法。它通过临时修改节点指针（找到当前节点左子树的最右节点，把它的右指针指向当前节点），在遍历完节点后恢复原状。优点是空间复杂度做到了 O(1)，不依赖栈；缺点是实现复杂，尤其是中序和后序的 Morris 版本难写且容易出错。

我的建议是：把它当进阶内容了解即可。日常刷题和工作里，递归和迭代版本已经能覆盖绝大多数场景。真遇到明确要求 O(1) 空间的场景，再拿出来用。

3.5 用一个完整的例子跑一遍

光说理论不够，拿一棵具体的树手动推一遍。

假设有如下二叉树：

1 / \ 2 3 / \ \ 4 5 6

前序遍历（根左右）：访问 1，进入左子树；访问 2，进入左子树；访问 4；回 2，访问 5；回 1，进入右子树；访问 3，进入右子树；访问 6。结果是 1、2、4、5、3、6。

中序遍历（左根右）：进入 1 的左子树；进入 2 的左子树；访问 4；访问 2；访问 5；访问 1；进入 3 的右子树；访问 6；访问 3。结果是 4、2、5、1、6、3。

后序遍历（左右根）：进入 1 的左子树；进入 2 的左子树；访问 4；进入 2 的右子树；访问 5；访问 2；进入 3 的右子树；访问 6；访问 3；访问 1。结果是 4、5、2、6、3、1。

你可以对照这个例子检查自己写的任何代码输出是否一致，这个树我调试时用了很多次，作为简单的验证用例很可靠。

4. 应用场景逐个拆解：什么时候用哪种遍历

这是这篇文章的重点。前序、中序、后序不只是三个“顺序”的排列组合，它们各自的执行时机，正好对应了不同场景的处理需求。

4.1 前序遍历的核心应用：需要“先处理根，再处理子树”的场景

前序遍历的第一个典型场景是二叉树的序列化。

什么是序列化？就是把树结构转换成字符串或字节流，以便传输或存储，之后还能还原成一棵完全一样的树。序列化需要一种能完整描述树结构的方式。前序遍历天然适合，因为根节点在最前面，反序列化时第一眼就能确定根节点，然后根据标记递归重建左右子树。

具体做法是：以前序遍历顺序输出节点值，遇到空节点输出一个特殊标记（比如#）。例如上面那棵树可以序列化为1,2,4,#,#,5,#,#,3,#,6,#,#。反序列化时，从前向后读取，第一个值就是根，接下来按前序规则递归还原左子树和右子树。这个方案可逆、无歧义，是很多框架里序列化二叉树的默认选择。

前序遍历的第二个典型场景是复制/克隆一棵二叉树。你要创建一棵新树，必须先把当前节点复制一份，再把左右子树递归复制出来。这个“先创建根，再创建孩子”的顺序，完全契合前序遍历。

第三个场景是打印目录结构。终端里用 tree 命令输出目录树时，你会先打印父目录，再进入子目录，然后继续深入。这不就是前序遍历吗？先根、再递归子树。

我自己做文件系统相关功能时，看到一个目录树就自然会想到前序遍历，因为这些场景都符合“先处理当前节点，再做子任务”的规律。

4.2 中序遍历的核心应用：二叉搜索树的有序输出

中序遍历最有名的性质是：对一棵二叉搜索树做中序遍历，得到的结果是一个升序序列。这是因为二叉搜索树定义了左子树所有节点值小于根节点，根节点小于右子树所有节点。中序的“左根右”顺序恰好把节点按从小到大排列出来。

这个性质对应了大量应用场景。

第一个场景是校验一棵树是否是二叉搜索树。做法很简单：对树进行中序遍历，检查结果序列是否严格递增。只要出现一个降序的位置，这棵树就不是二叉搜索树。这个思路实现简单、正确性直观，比递归比较“所有左子树节点小于根”要省事得多。

第二个场景是寻找二叉搜索树的第 K 小元素。中序遍历到第 K 个节点时，正好就是答案。只需要写一个带计数器的中序遍历，遍历到第 K 个节点就提前停下来。

第三个场景是表达式树的求值与还原。如果一棵表达式树中，内部节点是运算符，叶子节点是数字，那么中序遍历得到的就是人眼熟悉的中缀表达式，比如3 + 4 * 2。这符合我们的阅读习惯。当然，中缀表达式有个问题：它需要括号来消除歧义，所以纯粹的中序遍历输出表达式时，要额外注意添加括号。这一点在下一个小节展开。

4.3 后序遍历的核心应用：自底向上处理子树

后序遍历最大的特点是“先处理完左右子树，最后回到根节点”。这个顺序决定了它特别适合自底向上的处理场景。

最典型的场景是删除整棵树。在 C 或 C++ 这类需要手动释放内存的语言里，删除一棵树时绝对不能先删除根节点——根节点删了，子节点就找不到了。正确的顺序是：先递归删除左子树、删除右子树，然后再释放根节点。这是后序遍历的经典案例。即使现在用 Python、Java 这类有垃圾回收的语言，不需要手动释放内存，但这个逻辑在管理树中持有的资源（比如文件句柄、连接对象）时依然成立。

第二个典型场景是计算树的高度/深度。一棵二叉树的高度定义为 max(左子树高度, 右子树高度) + 1。要算根节点的高度，先得知道左右子树的高度，再把较大者加一。这个“先算子树，再算根”的模式就是后序遍历。同理，统计子树节点个数、求每个子树中满足条件的节点数，都是后序思路。

我给一个生活化类比：后序遍历就像把一摞盘子从洗碗池收进柜子。你得先把最上面的盘子（可以类比为最下层子树）一个个拿下来，最后才能把底下的盘子（根节点）抽出来。顺序反了就全塌了。

第三个场景是后缀表达式求值。把表达式树后序遍历，得到的就是后缀表达式（逆波兰表达式），比如3 4 2 * +。后缀表达式的优点是不需要括号，也没有优先级歧义，用栈配合小板凳就能直接求值：遇到数字压栈，遇到运算符弹出两个操作数计算结果再压栈。编译原理里，很多语法树生成代码时也常用后序遍历，因为子表达式的值必须先计算出来，父表达式才能用得上。

4.4 用遍历序列反推二叉树，以及“为什么前序+后序不行”

关于遍历序列，还有一个很有意思的应用：根据遍历结果重构二叉树。

• 前序序列 + 中序序列，可以唯一确定一棵二叉树。
• 后序序列 + 中序序列，也可以唯一确定一棵二叉树。
• 前序序列 + 后序序列，不能唯一确定一棵二叉树（除非原树是满二叉树）。

为什么前序+后序不行？因为前序能确定根在第一位，后序能确定根在最后一位，但它们都只给出了“根”和“子树整体位置”的信息，缺失了“左右子树如何划分”的信息。中序序列恰好提供了左右子树的分界线：根节点左边是左子树，右边是右子树。所以需要中序参与，才能唯一还原。

这个规律在刷题时特别有用。遇到“由遍历序还原二叉树”的题目，先想想它给的是哪些序列组合，再决定算法怎么写。如果只给前序和后序，题目大概率是要你判断“是否能构成唯一二叉树”或“有多少种不同形态”。

4.5 应用场景速查表

为了日常查阅方便，我把上面这些应用整理成一张速查表：

这张表配合前面几部分的描述，基本能回答“二叉树遍历分别有什么应用场景”这个问题了。

5. 常见问题与调试技巧实录

5.1 如何验证遍历算法写对了

我自己调试遍历代码时，会准备一棵手工形态可预期的树，比如第 3.5 节那棵1-2-3-4-5-6结构的树。先用笔在人脑中走一遍，记录期望输出，然后运行代码对照。这里有一个小技巧：写一个简易的可视化输出函数，把树的形状打印出来，同时输出三种遍历序列。这样有问题时可以快速定位是遍历逻辑错了，还是树建错了。

有时候建树过程本身就有问题。比如用数组建树时，判断左右孩子的索引写错了，树的形态和预想的不一致，遍历结果自然不对。所以验证遍历算法的第一步，是先确认树的结构本身没问题。

5.2 递归爆栈：什么时候该换成迭代

递归遍历虽然在代码上很简洁，但在深度非常大的树上会有风险。Python 默认的递归深度通常是一千层左右，如果你的树退化成链表状，深度超过这个数就会抛出递归深度错误。Java、C++ 虽然栈空间更大，但极端情况下依然可能栈溢出。

遇到这类问题，替换成迭代版本就可以了。三种遍历的迭代写法在第 3 部分已经给过思路。我个人的经验是：如果是 LeetCode 刷题，递归通常够用；如果是处理线上数据量很大的树形结构，迭代版本更稳妥。写迭代前序遍历和中序遍历比较轻松，迭代后序如果一时想不起来双栈法，就写状态标记法，正确率更高。

5.3 空节点和 None 的处理

遍历代码中关于空节点的处理，有一个常见问题：if not root和if root is None的区别。前者会把“节点值为 0”和“空节点”混在一起，只要值为 0 就被当成空节点处理了。

严格来说，判断“这是不是一棵空子树”应该用if root is None，不要用if not root。因为二叉树的节点值完全可能为 0，if not root会把值为 0 的节点错误地当作空节点跳过。这个坑我在帮别人排查代码时见过不止一次。

另外，在前序序列化场景中，空节点标记本身也有讲究。你用什么字符表示空节点，反序列化时就必须严格对称。比如前序序列化用#表示空节点，那么反序列化时看到一个#就要返回空子树，否则整棵树的还原就会错位。

5.4 练习顺序建议

最后聊一点学习路径。想彻底掌握三种遍历，不要只靠看文章。我的建议是：

第一步，手写一棵三层二叉树，自己用笔写出三种遍历结果。 第二步，用递归实现三种遍历，输出结果和手算对照。 第三步，用迭代实现三种遍历，特别是中序和后序。 第四步，做几道经典题目巩固，比如求树的最大深度（后序思路）、验证二叉搜索树（中序思路）、二叉树序列化（前序思路）。

每道题做完之后，想一想：这题为什么能用这个遍历？它利用了哪个遍历的哪个特性？这样把“会写”升级成“会选”，才是真正掌握。

我个人在实际项目中的体会是：遍历顺序的选择，本质上是在回答一个问题——“你需要在什么时候拿到信息？”需要先知道父节点信息才能处理子树，就选前序；需要按节点的自然顺序输出，就选中序；需要先拿到子节点结果再汇总给父节点，就选后序。记住这个原则，比死背一百道题都有用。

最后再分享一个小技巧：写遍历相关的递归函数时，尽量让函数返回值“完整描述当前子树”，比如返回子树高度、子树节点个数、子树有序数组，而不是只返回一个布尔值或者只打印不返回。这样写出来的代码可复用性强，后面做各种树形统计题都会顺手很多。遍历不是终点，它是你处理一切二叉树问题的基础设施。