彻底讲透二叉树遍历：前序中序后序的递归与迭代核心

二叉树这玩意，我在实战里见过太多背模板、默口诀的人。前序、中序、后序，嘴上说得顺溜，手上一写就乱。其实问题出在没理解“序”到底在表达什么——不是遍历方法的名称，而是根节点出现在遍历序列里的位置。一旦想通这一点，递归、迭代、重建树、序列化，全都能串起来。这篇就用最直接的方式来拆，先概念、再代码、后实战，把二叉树和三种遍历彻底讲透。

1. 先从“什么是二叉树”说起

1.1 一棵树和一个递归的自我

二叉树不是一个能被循环for两三下遍历完的普通集合，它天生是一种递归结构。你要想理解它，得先接受一个听起来像套娃的定义：

二叉树要么是空树，要么由一个根节点和左右两棵互不相交的二叉树组成。

注意这里有个陷阱——定义里用了“二叉树”来解释“二叉树”。不是循环定义糊弄人，而是它本来就长这样。拿文件系统举例，你打开一个文件夹，里面有子文件夹，子文件夹里还有子文件夹，这就是一棵树，只是文件夹可以有任意多个孩子。而二叉树是一次只允许最多挂两个孩子的特化版本。

节点的概念也简单：

• 根节点：树最顶层的入口，就像公司组织架构里的那个最终汇报对象。
• 叶子节点：左右孩子都是空的节点，没有下属、不用继续往下展开。
• 子树：把任意节点的左孩子当成新“根”往下看，它自己就是一棵完整的树。
• 深度：从根到某个节点经过的边数，根节点的深度为0。
• 高度：一棵树的高度是根到最远叶子经过的节点数，通常理解为一共有多少层。

二叉树的“二叉”限制，让它产生了一些非常规整的数学性质。比如第 n 层最多有 2^(n-1) 个节点。深度为 h 的二叉树最多能装 2^h - 1 个节点。这也是为什么“完全二叉树”能用数组存储，因为这种树的结构足够规则，下标能精确表达父子关系。

1.2 为什么面试和工程都要考二叉树

从实际工作量来看，大部分业务开发并不会天天手写二叉树。但“遍历一棵二叉树”几乎是所有后续算法问题的入口，它训练的是你对递归和分治的直接手感。

• 数据库里的 B+ 树是树的变种，查数据躲不开。
• 编译器里的表达式树、语法树，本质就是二叉树或者多叉树。
• 操作系统的文件目录、路由表的 trie，全是树的思想。
• 搜索引擎的倒排索引、推荐系统的行为树，底层也离不开树结构。

面试用二叉树来刷人，因为它能一层层剥离你的基本功。树的遍历代码不满二十行，却能把几个核心能力全考一遍：递归写的熟不熟、循环和栈结合得好不好、边界条件能不能想干净。所以你不是在为面试学二叉树，而是在用二叉树补自己的数据结构地基。说得更直白一点，遍历玩明白了，动态规划里“子问题拆解”的思路都会顺很多，因为树的递归过程和状态转移实在长得太像了。

2. 三种遍历方式的本质：访问顺序的游戏

前序、中序、后序，这三个名字里的“序”字，指的是“根节点被输出的时刻”。左孩子和右孩子的访问顺序永远是“先左后右”，唯一变化的就是根什么时候被拿出去。

看三个遍历的输出名，立刻建立第一反应：

• 前序：根 -> 左 -> 右
• 中序：左 -> 根 -> 右
• 后序：左 -> 右 -> 根

把整棵树应用的规则也一样。树里的每个节点的访问顺序都必须遵循这个大规则，递归套递归，最后形成全树的访问序列。

2.1 前序：先来到，再探索

前序遍历的思想是自顶向下。走进一个节点，先把这个节点的值记下来，然后再去钻左子树，左子树钻完再钻右子树。它的路径天然包含了“根在前”的信息。最典型的应用场景是树的复制：你要克隆一棵树，必须先知道根节点是谁，才能给它分配内存、挂左右孩子。文件系统拷贝目录时先建父目录再建子目录的逻辑也是如此。还有序列化，我们后面会重点讲，前序遍历配合空节点标记，可以完整地把一棵树变成字符串再还原。它为什么适合？因为前序序列的第一个元素永远是整个树的根节点，光这一点就给了重建的入口。

2.2 中序：左中右，排序的关键

中序遍历输出的是“左子树全部节点 -> 根 -> 右子树全部节点”。如果把一棵二叉搜索树（左小右大）做中序遍历，你会发现你拿到的是一个严格递增的有序序列。这个性质在整个计算机领域都是最靓的仔：因为有了中序，你可以直接决定一棵 BST 里第 k 小的元素是不是就是第 k 次访问到的节点。

表达式求值场景也常和中序有关。像3 + 5 * 2这个表达式，中序遍历表达式树能还原出标准的中缀表达式，但需要注意加括号的问题，不然运算符优先级会错。中序遍历还经常配合其他遍历一起用——比如用前序或后序找根，再用中序去切分左右子树范围，这个玩法在重建二叉树里属于必考题，后面详细展开。

2.3 后序：先孩子后自己

后序遍历的思想是自底向上。先把左右子树全部搞定，最后再处理根节点。最典型的一个应用：释放一棵树的内存。删除节点时如果一个节点还有孩子，你直接 free 它，那孩子就成了无法访问的孤儿。所以你必须先递归处理左子树、右子树，最后才释放根。操作系统删除目录也是一样，先删子目录，再删当前目录。

表达式求值的另一个经典路径也在这——后缀表达式。编译器和计算器会把中缀表达式转成后缀，因为后缀表达式的计算不需要括号、不需要优先级判断，只要一路压栈弹栈就行。它的本质结构就是从后序遍历的顺序来的。

2.4 一句话记忆法

直接用“根的位置”来记：

这三个序里，前序和后序都是可以互相倒腾的，比如前序反转左右子树的访问顺序，就变成了镜像的“根右左”，后序从逆序看又很像前序。很多人学到最后会混淆，就是因为没抓住“根位置”这个核心锚点。

3. 递归实现：三行代码看穿遍历

先别上迭代，递归是理解遍历的最好语言。如果你已经会写递归，下面是三种遍历的完整实现；如果你还不熟，我会在代码后解释每一步在干什么。

3.1 前序遍历的递归代码

def preorder(root): if root is None: return [] return [root.val] + preorder(root.left) + preorder(root.right)

用列表相加的方式来写的，可能有人觉得不高效，但这是最直观的。看不惯也可以改成收集器模式：

def preorder(root): res = [] def dfs(node): if node is None: return res.append(node.val) dfs(node.left) dfs(node.right) dfs(root) return res

第二段代码把“前序”的开关就放在那一个append的位置上。这个位置决定了根是什么时候被收集。

3.2 递归到底在干嘛：一个隐形的栈

很多人写递归会死记，其实每次递归调用背后都压了一个函数栈帧。当你调用dfs(root.left)时，当前函数还没结束，它必须记住自己进行到哪一行、参数是什么、局部变量是什么，这些信息全部压在系统栈里。等左子树全部跑完，栈帧逐层弹出，才回到刚才的dfs(root.left)这一行，继续往下执行dfs(root.right)。

我画过一个生活化的类比，像进一个多层停车场：

• 你把车开到第一层，发现还有地下层，于是先把这层“记在脑子里”，往下走。
• 走到底层，没路了，开始原路返回。
• 返回途中每经过一层，就把这层的事情办了（比如看右边的车位），再继续往上返回。

前序是“下去之前先把这层看一眼”，中序是“从左边返回时再看这一层”，后序是“左右两边都回来之后再看这一层”。理解了这个过程，递归代码的顺序就不再需要背了。

具体拿一棵小树举例：

1 / \ 2 3 / \ \ 4 5 6

前序遍历的路径是：1 -> 2 -> 4 -> 5 -> 3 -> 6。模拟一下：根是1，先输出1，进入左子树；左子树的根是2，输出2，继续进入2的左子树；4没有左右孩子，输出4；回到2的右子树，输出5；回到根节点1的右子树，根3输出3，再进入左孩子空，进入右孩子6，输出6。整条线就是“一直往左钻，钻不动就往回退一步钻右边”。

中序遍历：4 -> 2 -> 5 -> 1 -> 3 -> 6。关键在于，你是先钻到最左边，发现不能再往左了，才第一次输出。所以第一个输出的往往是整棵树最左边的节点。

后序遍历：4 -> 5 -> 2 -> 6 -> 3 -> 1。全是子节点先出来，根节点压轴。

3.3 中序与后序的根行代码

中序的递归只挪一个append：

def inorder(root): res = [] def dfs(node): if node is None: return dfs(node.left) res.append(node.val) dfs(node.right) dfs(root) return res

后序同理：

def postorder(root): res = [] def dfs(node): if node is None: return dfs(node.left) dfs(node.right) res.append(node.val) dfs(root) return res

三个函数长得几乎一样，唯一的区别就是res.append这个操作在递归调用之间被放在了哪个位置。所以很多人学完递归就会发现，遍历本身不是难点，难的是理解调用栈的时机。

实战经验：递归虽然好懂，但一定要有“空节点处理”这个 base case。if node is None不是可有可无的防御代码，它是递归的终止条件。没有这一行，当访问到叶子节点的左孩子时，代码就会试图访问None.val直接报错。

递归写法适合快速答题和验证思路，缺点是当树特别深的时候，系统栈会被打爆。常见的处理方式是限制递归深度或用后面要讲的迭代法。

4. 迭代实现：手动维护栈的硬核玩法

面试中很多公司在问完递归之后，一定会追加一个要求：“不用递归，用迭代写一遍。”这不是故意刁难，而是考察你能不能看穿递归本质——递归就是在用系统栈，迭代就是把“栈”拿到自己手里控制。

4.1 前序迭代的最简写法

前序是最适合迭代的，因为它的访问顺序（根 -> 左 -> 右）和栈的先进后出行为天然吻合。你想下次先访问左子树，那就先把右子树压进栈，这样弹出的时候左子树会先出来。

def preorder_iter(root): if root is None: return [] res = [] stack = [root] while stack: node = stack.pop() res.append(node.val) if node.right: stack.append(node.right) if node.left: stack.append(node.left) return res

这里一定要记得先压右，再压左。因为栈是后进先出，压右子树先，左子树后，下一次循环弹出来的是左子树，正好符合“根左右”的顺序。

4.2 中序迭代的精髓：一路向左

中序的迭代是所有遍历里最容易写崩的。它的策略简单说就是：能往左就往左，把沿途节点全部压栈；当某一个节点左子树为空时，从栈里弹出它并输出，然后转向它的右子树。

def inorder_iter(root): res = [] stack = [] cur = root while cur is not None or stack: while cur is not None: stack.append(cur) cur = cur.left cur = stack.pop() res.append(cur.val) cur = cur.right return res

用之前的树跑一遍：cur 从1往左走，压入1、2、4；4的左孩子是空，弹出4输出，cur变成4的右孩子（空），内层循环结束；stack里还剩2、1，弹出2输出，cur变成2的右孩子5；压入5，变空，弹出5输出，再弹出1输出……整个过程你基本能听到“咔哒咔哒”弹栈的声音。这个思路是从树的最左下角“钻进去”，再一层层收网，非常经典。

4.3 后序迭代：两种思路

后序迭代最麻烦，因为根节点的输出被卡在左右子树全部完成之后。这里分享两种常用的写法。

方案一：两个栈，或者叫“根右左”的逆向输出

前序是根左右，如果改写成根右左，再整体反转输出，就是左右根。具体做法：

def postorder_iter_two_stack(root): if root is None: return [] res = [] stack = [root] temp = [] while stack: node = stack.pop() temp.append(node.val) if node.left: stack.append(node.left) if node.right: stack.append(node.right) while temp: res.append(temp.pop()) return res

第一步和上面的前序很像，只是这次改成先压左、再压右，弹出顺序变成“根右左”，最后把临时栈倒出来，刚好是“左右根”。这个方法不用记很多状态的切换，属于新手友好型。

方案二：只用一个栈，记录“上一次输出/访问的节点”

这个方案更省空间，但代码量稍大。核心思想是：只有两种情况可以输出当前节点，一是它的左右孩子都为空，二是它的左孩子或右孩子刚刚被访问过（说明下面已经全部处理完了）。

def postorder_iter_one_stack(root): res = [] stack = [] last_visited = None node = root while node is not None or stack: while node is not None: stack.append(node) node = node.left peek = stack[-1] if peek.right is not None and last_visited is not peek.right: node = peek.right else: res.append(peek.val) last_visited = peek stack.pop() return res

这个过程中需要时刻问自己一个问题：“右子树处理完了没有？”如果右子树为空，或者右子树刚刚被输出过，说明当前节点的左右两边都干完了，可以放心输出根节点。

4.4 层序遍历顺带提一嘴

严格说，层序和前中后序不在一个维度上，前中后序是深度优先，层序是广度优先。实现方式也从栈换成了队列。它输出的是一层层从左到右的顺序：上面的例树就是[1, 2, 3, 4, 5, 6]。层序通常用于求最大宽度、判断完全二叉树之类的问题，属于**广度优先搜索（BFS）**家族的入门题。但日常聊到树的遍历，大家经常把它一起带上，所以这里先留一个印象。

5. 遍历的实战应用：没有一次遍历是白写的

学习遍历最怕“学完就忘”，因为只当它是一道练习题。实际情况是遍历是很多树形问题的“地基技能”，下面用几个典型场景说透。

5.1 根据中序 + 前序/后序重建二叉树

面试高频题，也是一道能把你从“会写遍历”拉到“懂遍历意义”的题。给定前序和中序，如何恢复出唯一的二叉树？

关键信息拆解：

• 前序序列的第一个元素，一定是整棵树的根。
• 在中序序列中，这个根元素的位置把序列切成两半：左边是根的整棵左子树，右边是根的整棵右子树。
• 于是你就可以从前序序列里分别切出左子树的部分和右子树的部分，递归去构建。

用上面的例子树：

前序：[1, 2, 4, 5, 3, 6] 中序：[4, 2, 5, 1, 3, 6]

前序的第一个1是根。在中序里找1，左边是[4, 2, 5]，右边是[3, 6]。所以左子树的中序范围是[4, 2, 5]，长度为3；右子树中序范围是[3, 6]。接着在前序里从左往右取3个元素，得到左子树的前序是[2, 4, 5]，剩下的是右子树的前序[3, 6]。继续递归，树就成型了。Python实现：

def build_tree(preorder, inorder): if not preorder: return None root_val = preorder[0] root = TreeNode(root_val) idx = inorder.index(root_val) left_len = idx # 切分前序 left_pre = preorder[1:1 + left_len] right_pre = preorder[1 + left_len:] # 切分中序 left_in = inorder[:idx] right_in = inorder[idx + 1:] root.left = build_tree(left_pre, left_in) root.right = build_tree(right_pre, right_in) return root

这题会告诉你一个深刻结论：“中序 + 前序”或“中序 + 后序”都能唯一确定一棵二叉树，但如果只给前序和后序，则无法唯一确定。原因很简单，前序和后序都能确定根的位置，但切分左右子树边界时都缺少足够信息。比如一个只有两层的树，1是根，只有一个孩子是2，那这个孩子是左还是右，光靠前后序遍历看不出来。而中序里这个孩子落在根的左边还是右边，一目了然。

5.2 序列化与反序列化的思路

序列化第一步要解决一个问题：普通前序序列无法区分“空子树”和“没有遍历到的子树”，所以必须用一个特殊符号，比如#，来表示空节点。

序列化用前序最顺：1,2,#,4,#,#,3,#,6,#,#，每个节点遇到空就补#。反序列化时，每次读一个值，按前序规则先创建根，再递归建左子树，再递归建右子树，遇到#就返回空。这样字符串能完整还原树的形状。

也可以直接整体存前序和中序两个序列，反序列化时用上面的重建逻辑跑一遍。工程上两者都有用，但“前序+空标记”更省存储，也更常见。

5.3 前中后序信息在工程里的典型场景

• 表达式求值器：表达式树的后序对应后缀表达式，用栈一行行算即可得到结果，不需要括号。
• HTML/XML 解析器：DOM 树的深度优先遍历逻辑和前序很像，遇到开始标签进入子节点，遇到结束标签返回父节点。
• 二叉搜索树找第 K 小元素：中序遍历天然有序，一边遍历一边递减 K，命中时输出即可，时间复杂度 O(n)。
• 判断一棵树是否平衡：后序遍历时，先递归拿左右子树的高度信息，再在根节点处判断高度差，避免重复遍历。

很多读者可能觉得这些场景离业务远，但数据库索引、路由表、正则表达式引擎，核心结构都是“某种树”，而树的算法精不精，看的就是遍历的底子。遍历不是题目，是通往更复杂树算法的一把钥匙。

6. 常见问题与避坑实录

很多人在树相关的代码上花时间，其实不是卡在思路上，而是卡在细节的实现和边界处理上。这里列几个我实际写代码时踩过的坑，每条都是把代码交给运行环境之后形成的血泪教训。

6.1 递归爆栈

我在本地写过一个极端测试：构造一棵完全退化的斜树，每个节点只有右孩子，一共构造足够深。递归前序直接抛出了“maximum recursion depth exceeded”的异常。在需要通过文件解析递归构建树的基础上，这个问题更加常见。解决方案有两种：

• 加递归深度限制，用sys.setrecursionlimit()临时放宽限制。治标。
• 改写成迭代遍历，用显式栈。治本。

生产环境里，递归虽然代码写起来最舒服，但系统栈通常是受限的，深度到一定程度就崩。真正处理深度不确定的数据时，我一般选显式栈的迭代实现。

6.2 空指针和循环边界

我看过太多初版代码，在进入节点后直接访问node.left.val，完全没判空。二叉树里有一个“空节点”是合法存在的，特别是叶子节点下面挂的都是 None，这个 None 就是递归出口。迭代遍历里也要留意空栈的问题，比如中序迭代的循环条件while cur is not None or stack，少写任何一个都会漏掉边界的后半段。

6.3 斜树这种极端形态

二叉树并不都是满的、完整的。最极端的情况就是每个节点只带一个孩子，一路歪到底，这种树叫退化树，形状上基本等价于链表。遍历起来递归层次极深，深度等于节点数。遇到这种用例，递归写法非常危险。刷题时很多人用常规例子测没问题，一提交就内存栈溢出，多半就是测试用例包含了这种斜树形态。

6.4 遍历模板的变式：N叉树、属性统计

前中后序这三个名词通常针对二叉树。但如果扩展到 N 叉树，很多规则会变。比如 N 叉树没有“中序”，因为中间位置无法定义。N 叉树只有前序、后序、层序。所以从二叉树切到 N 叉树时，不要强行套模板。工程上常见的文件目录遍历就是典型 N 叉树，递归遍历逻辑中序完全不存在。

另一个常见变形是“边遍历边统计属性”。比如遍历过程中记录当前路径权值和、找最大路径、或者判断某棵树是否是另一棵树的子树。这些都不是简单输出值的遍历，而是遍历核心逻辑上加上剪枝和状态收集，建议单独练习。

还有一种很常见的误区：把前序写成中序，代码逻辑对不出结果。调试时最好的办法是打印调用轨迹，或者在小规模树上手算一遍序列，再对照输出。遍历这种基础题，宁可先跑小样例，也不要去猜答案。

6.5 什么时候该用哪种遍历

这是很多初学者最大的困惑。我给一个非常实际的决策标准：看你处理“根节点”和“孩子节点”之间的关系，根节点信息是否依赖孩子节点。

• 如果需要先知道根节点才能处理孩子，比如复制树、序列化，选前序。
• 如果处理根节点时需要先拿到左右子树的结果，比如求树的高度、判断平衡、删除节点，选后序。
• 如果只想要有序的数据流，比如二叉搜索树从小到大输出，选中序。

这个决策标准是我个人的经验总结，不算定理，但实践中非常好用。凡是“统计类”“聚合类”的操作，优先想后序；凡是“分发类”“构造类”的操作，优先想前序。

最后再分享一个控制递归越界的小技巧：如果你用后序来判断一棵树是否平衡，千万别在每层递归里再独立计算左右子树的高度，那样时间复杂度会变成 O(n^2)。正确做法是在递归后序的同时，自底向上返回子树高度，这个高度是“边算边往上送的”，不是每层重新去扫一遍子树。这类细节是分析和优化树问题的分水岭。