很多人学二叉树最先接触的就是前序、中序、后序遍历这三种遍历方式。“根左右、左根右、左右根”这种口诀背得很熟可真到了刷题、写工程或者面试手撕代码的时候反而容易懵为什么这个场景要用中序为什么那个场景要用后序三种遍历的顺序到底怎么来的这篇文章就把二叉树的前序、中序、后序遍历一次讲透。不讲虚的直接围绕三件事展开三种遍历的本质区分是什么代码层面递归和迭代分别怎么写最重要的是——它们各自到底在什么场景下派上用场。我会结合序列化、表达式求值、二叉搜索树处理、树形结构删除等真实例子把每个遍历的“性格”和“适用场景”说清楚。适合刚学数据结构的学生、准备算法面试的开发者以及工作中需要手写树形结构处理的工程师。1. 三种遍历的本质根节点在什么时候被访问1.1 从二叉树的结构看遍历顺序先明确一个基本认知二叉树由三部分组成——根节点、左子树、右子树。遍历一棵树本质上就是把这三部分都“过”一遍。而前序、中序、后序这三种遍历方式唯一的区别就是根节点被访问的时机。前序遍历也就是先序遍历先访问根节点然后遍历左子树最后遍历右子树。缩写就是“根左右”。中序遍历先遍历左子树然后访问根节点最后遍历右子树。缩写是“左根右”。后序遍历先遍历左子树然后遍历右子树最后访问根节点。缩写是“左右根”。你看左子树永远在右子树前面被遍历这个顺序在三种遍历里是不变的。变得只有一件事根节点排在第几个。前序根在最前中序根在中间后序根在最后。这就是全部的秘密。1.2 用递归展开的方式理解顺序有人可能会问那左右子树内部又是怎么遍历的答案是——递归地按同样的规则遍历。举个例子一棵树结构如下注意这里不涉及具体数值只描述结构根节点 AA 的左子树以 B 为根B 有一个左孩子 DA 的右子树以 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, val0, leftNone, rightNone): 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 应用场景速查表为了日常查阅方便我把上面这些应用整理成一张速查表遍历方式执行时机适用场景典型应用前序遍历先根再左后右需要先处理当前节点再处理子树序列化、克隆树、打印目录树中序遍历先左再根后右需要按大小/逻辑顺序访问节点二叉搜索树升序输出、验证BST、求第K小、中缀表达式后序遍历先左再右最后根需要先处理完全部子树再回到根删除根节点释放资源、求树高、统计子树信息、后缀表达式这张表配合前面几部分的描述基本能回答“二叉树遍历分别有什么应用场景”这个问题了。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。因为二叉树的节点值完全可能为 0if not root会把值为 0 的节点错误地当作空节点跳过。这个坑我在帮别人排查代码时见过不止一次。另外在前序序列化场景中空节点标记本身也有讲究。你用什么字符表示空节点反序列化时就必须严格对称。比如前序序列化用#表示空节点那么反序列化时看到一个#就要返回空子树否则整棵树的还原就会错位。5.4 练习顺序建议最后聊一点学习路径。想彻底掌握三种遍历不要只靠看文章。我的建议是第一步手写一棵三层二叉树自己用笔写出三种遍历结果。 第二步用递归实现三种遍历输出结果和手算对照。 第三步用迭代实现三种遍历特别是中序和后序。 第四步做几道经典题目巩固比如求树的最大深度后序思路、验证二叉搜索树中序思路、二叉树序列化前序思路。每道题做完之后想一想这题为什么能用这个遍历它利用了哪个遍历的哪个特性这样把“会写”升级成“会选”才是真正掌握。我个人在实际项目中的体会是遍历顺序的选择本质上是在回答一个问题——“你需要在什么时候拿到信息”需要先知道父节点信息才能处理子树就选前序需要按节点的自然顺序输出就选中序需要先拿到子节点结果再汇总给父节点就选后序。记住这个原则比死背一百道题都有用。最后再分享一个小技巧写遍历相关的递归函数时尽量让函数返回值“完整描述当前子树”比如返回子树高度、子树节点个数、子树有序数组而不是只返回一个布尔值或者只打印不返回。这样写出来的代码可复用性强后面做各种树形统计题都会顺手很多。遍历不是终点它是你处理一切二叉树问题的基础设施。