如果你写过几道和二叉树相关的 C 题目大概率见过这三段长得差不多的递归代码前序、中序、后序区别只是一行输出语句放在递归调用的前面、中间还是后面。不少同学能把这几个模板背下来但被问到“为什么放在中间就是中序”“为什么迭代版要自己维护一个栈”时反而说不清楚。这篇文章想把这层窗户纸捅破。我会从一棵具体的小树开始把三种遍历的输出结果和代码对应起来再手动推演递归调用栈的完整过程然后给出自己管理栈的迭代实现以及层序遍历的队列写法。最后聊一聊这些遍历在真实工程里到底能干什么还有我在写这类代码时踩过的几个坑和研究出的验证思路。适合刚学完结构体和指针、想系统整理二叉树的 C 学习者也适合准备面试时想彻底理解遍历本质的开发者。1. 先搞清楚“根在什么时候被访问”1.1 一棵小树三种打印结果先给出一棵最普通的二叉树后面所有代码都拿它做例子A / \ B C / \ \ D E F所谓“前序、中序、后序”字面意思是根节点的访问时机不同根在前叫前序根在中间叫中序根在最后叫后序。左右子树的相对顺序永远是先左后右这一点很多人容易忽略。三种遍历的输出结果分别是遍历方式访问顺序输出结果前序根左右A - B - D - E - C - FA B D E C F中序左根右D - B - E - A - C - FD B E A C F后序左右根D - E - B - F - C - AD E B F C A建议你先自己照着树手动走一遍中序从 A 出发先进入左子树 BB 还有左子树 DD 没有孩子了所以第一个输出 D回到 B输出 B再进 B 的右子树 E输出 E回到 A输出 A进入右子树 CC 没有左孩子输出 C再进 C 的右孩子 F输出 F。整个过程就是“左 - 根 - 右”的不断重复。1.2 递归版本把整棵树拆成三个动作理解二叉树遍历的关键是意识到任何一棵二叉树都可以拆成三个部分根、左子树、右子树。而每一棵子树本身又是一棵二叉树于是可以继续拆下去直到拆出空节点。这就是递归能解决遍历问题的前提。C 里二叉树最常见的结构体定义是这样struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} };三个递归遍历函数如下void preorder(TreeNode *root) { // 前序根 - 左 - 右 if (root nullptr) return; cout root-val ; preorder(root-left); preorder(root-right); } void inorder(TreeNode *root) { // 中序左 - 根 - 右 if (root nullptr) return; inorder(root-left); cout root-val ; inorder(root-right); } void postorder(TreeNode *root) { // 后序左 - 右 - 根 if (root nullptr) return; postorder(root-left); postorder(root-right); cout root-val ; }从代码可以看到三个函数的结构几乎一样唯一区别是“访问根”这一行代码的位置。前序放在两次递归调用之前中序放在两者之间后序放在两次递归调用之后。这里有个初学者很容易绕进去的点为什么中序函数里先调用inorder(root-left)再打印再调用inorder(root-right)就能保证“左根右”因为递归会先一路深入到最左边的节点把整个左子树完整处理完才会返回到当前层执行打印语句。也就是说打印语句被递归调用“夹住”了所以它的执行时机天然落在左子树之后、右子树之前。想通这一点后面看迭代版就轻松很多。递归版遍历的时间复杂度是 O(n)每个节点恰好被访问一次空间复杂度是 O(h)h 是树的高度递归最深时需要占用 h 层函数调用栈空间。这个复杂度在二叉树上已经是最优量级后面讲的迭代版也不会突破这个上限。2. 递归遍历时函数调用栈到底发生了什么2.1 中序遍历的手动推演很多教程只给递归代码不解释递归过程。这里我用中序遍历手动推演一遍调用栈的变化因为中序的“中间访问”最能体现栈的特性。还是那棵树调用inorder(A)进入inorder(A)A 非空先调用inorder(A-left)也就是inorder(B)A 这一层被压入系统调用栈等待返回。进入inorder(B)B 非空先调用inorder(B-left)也就是inorder(D)B 这一层入栈。进入inorder(D)D 非空调用inorder(D-left)D-left 是 nullptr立即返回。输出 D。调用inorder(D-right)空返回。inorder(D)彻底结束返回值给上一层D 出栈。回到inorder(B)的“中间位置”输出 B。调用inorder(B-right)也就是inorder(E)输出 E然后返回。inorder(B)结束B 出栈回到inorder(A)的中间位置输出 A。调用inorder(A-right)也就是inorder(C)C 输出后进入 F输出 F最后返回。整个过程输出D B E A C F。递归的本质就是“系统帮你维护了一个栈”。每次函数调用就把当前函数未执行完的状态压入栈中返回时再从栈里恢复状态。所以递归版后序虽然看起来是先处理完子树再打印根实际执行顺序也完全由这个栈决定。2.2 为什么递归看上去这么直观从上面的推演能看出递归版遍历“把复杂问题分解成同构子问题”代码写出来就是对“根、左、右”三个动作的排列组合几乎不需要考虑下一步怎么走。这也是为什么教科书首选递归实现。但递归有个隐含条件系统栈大小不是无限的。如果一棵二叉树退化成链式结构比如每个节点都只有右孩子递归深度会达到 n当 n 很大时非常容易触发栈溢出。C 默认函数调用栈一般在 1MB 到 8MB 左右具体看编译环境和操作系统一个递归帧就算只占几十字节几十万层也会把栈压爆。所以我们在刷题或写组件时除了递归版还应该掌握迭代版。迭代版需要自己在堆上创建栈结构堆空间比系统栈大得多可控性也更高。这不只是为了面试有些生产环境确实会禁用较深的递归或者编译选项设置了很小的栈空间限制。2.3 一个容易误解的点遍历顺序不等于节点存储顺序有些初学者会以为“前序遍历就是按从上到下、从左到右的顺序打印”这是错的。从上到下、从左到右的层次关系那是层序遍历不属于前中后序的讨论范围。前中后序是基于“根什么时候访问”划分的和树的几何层次没有直接关系。就拿树里最右边的 F 节点来说它在前序输出中排在第 6 位而在中序中也排第 6 位但后序中它排第 5 位说明“位置靠右”并不意味着只能最后被处理。理解这一点才能真正明白三种遍历的差别。3. 迭代遍历自己管理栈的完整推演3.1 前序迭代最简单的栈应用前序的顺序是“根 - 左 - 右”。既然根先被访问那我们可以先把根节点压入栈然后循环弹出栈顶节点并输出再把它的右孩子和左孩子依次压入栈。这里有个关键点栈是后进先出所以想让左孩子先被处理就必须先压右孩子、再压左孩子。void preorderIterative(TreeNode *root) { if (root nullptr) return; stackTreeNode* st; st.push(root); while (!st.empty()) { TreeNode *node st.top(); st.pop(); cout node-val ; if (node-right) st.push(node-right); if (node-left) st.push(node-left); } }用例子验证A 入栈弹出 A 输出压入 C 和 B栈顶是 B弹出 B 输出压入 E 和 D弹出 D 输出D 没有孩子弹出 E 输出最后弹出 C压入 F再输出 F。结果 A B D E C F和前序递归版一致。3.2 中序迭代难点在于“从左子树回来再访问根”前序迭代之所以简单是因为根节点最先被处理压栈顺序直接决定了访问顺序。中序不一样根在左子树之后才被访问这意味着我们不能在第一次遇到根节点时就输出它得先把整个左子树走完再回来输出根。维护一个cur指针表示当前正在处理的节点。外层循环条件为cur ! nullptr || !st.empty()void inorderIterative(TreeNode *root) { stackTreeNode* st; TreeNode *cur root; while (cur ! nullptr || !st.empty()) { while (cur ! nullptr) { st.push(cur); cur cur-left; } cur st.top(); st.pop(); cout cur-val ; cur cur-right; } }内层循环不断把当前节点和它的左孩子压栈直到走到最左边。之后弹出栈顶节点这个节点就是当前子树的最左节点输出它然后把cur指向它的右孩子。注意右孩子可能为空这样下一轮外层循环就会继续弹栈回到上一层节点。手动跑一遍A 入栈B 入栈D 入栈D 左孩子为空弹出 D 输出cur 指向空弹出 B 输出cur 指向 E把 E 入栈E 左孩子为空弹出 E 输出最后弹出 A 输出cur 指向 C……结果正确。这段代码最容易写错的地方是把while (cur ! nullptr)写成if那样就没法一路走到最左下角。3.3 后序迭代两种实现思路后序是三种里迭代最不那么直观的。先给一个最容易理解的双栈思路第一个栈负责遍历第二个栈负责反转访问顺序。void postorderIterative(TreeNode *root) { if (root nullptr) return; stackTreeNode* st1, st2; st1.push(root); while (!st1.empty()) { TreeNode *node st1.top(); st1.pop(); st2.push(node); if (node-left) st1.push(node-left); if (node-right) st1.push(node-right); } while (!st2.empty()) { cout st2.top()-val ; st2.pop(); } }思路来自观察后序是“左 - 右 - 根”反过来的逆序是“根 - 右 - 左”。如果我们能先得到“根右左”的序列再整体反转就得到了“左右根”。第一个栈做的正是“根右左”的遍历根入栈弹出后将左右孩子入栈由于栈后进先出右孩子会被先处理。处理结果压入第二个栈第二个栈最后弹出时就完成了反转。另一个常见思路是单栈加一个prev指针标记上一个访问过的节点。当栈顶节点的右孩子为空或者右孩子刚刚访问过时说明左子树和右子树都处理完了可以输出根节点否则继续把右孩子和左孩子压栈。这个写法更省空间但分支逻辑多一些面试时双栈版更容易现场写对。3.4 一个统一写法给每个节点打标记有没有办法让三种遍历用同一套迭代模板有而且很优雅栈里不仅存节点指针还存一个 bool 标记表示该节点是否已经“准备好被访问”。第一次遇到时为 false把它和它的孩子按某个顺序重新压栈第二次遇到时标记为 true直接输出。void uniformTraversal(TreeNode *root, int mode) { if (root nullptr) return; stackpairTreeNode*, bool st; st.push({root, false}); while (!st.empty()) { auto cur st.top(); st.pop(); TreeNode *node cur.first; bool visited cur.second; if (node nullptr) continue; if (visited) { cout node-val ; } else { if (mode 0) { // 前序 if (node-right) st.push({node-right, false}); if (node-left) st.push({node-left, false}); st.push({node, true}); } else if (mode 1) { // 中序 if (node-right) st.push({node-right, false}); st.push({node, true}); if (node-left) st.push({node-left, false}); } else { // 后序 st.push({node, true}); if (node-right) st.push({node-right, false}); if (node-left) st.push({node-left, false}); } } } }这里的核心逻辑是栈是后进先出如果我们希望某个节点先被访问就必须把它最后压栈。前序希望“根、左、右”所以压栈顺序是“右、左、根”中序希望“左、根、右”所以压栈顺序是“右、根、左”后序希望“左、右、根”所以压栈顺序是“根、右、左”。这套模板的价值在于你不需要为每种遍历单独记忆一套迭代逻辑只要记住压栈顺序和访问期望相反即可。注意上面代码用了pairTreeNode*, bool和结构化绑定适用于 C17如果编译器标准是 C11可以把auto [node, visited]改成auto cur st.top(); st.pop(); TreeNode *node cur.first; bool visited cur.second;。4. 层序遍历队列出场树变成一组序列4.1 基础版逐节点输出前中后序的本质是深度优先搜索顺着一条路径走到黑再回头。层序遍历则是广度优先搜索一层一层扫过去。实现上需要把栈换成队列因为队列先进先出能保证先进入的节点先被处理正好符合从上到下、从左到右的顺序。void levelOrder(TreeNode *root) { if (root nullptr) return; queueTreeNode* q; q.push(root); while (!q.empty()) { TreeNode *node q.front(); q.pop(); cout node-val ; if (node-left) q.push(node-left); if (node-right) q.push(node-right); } }对示例树输出A B C D E F。这里要注意层序输出的 C 排在 D 和 E 前面哪怕 D 和 E 在视觉上更靠左。原因很简单B 和 C 同时在第 1 层B 先出队它的孩子 D、E 排到 C 后面接着 C 出队F 继续排到末尾。所以第 2 层的节点整体排在第 0 层节点后面但第 2 层内部的顺序依然是左到右。4.2 升级版按层分组输出很多场景不满足于“逐节点输出”而是需要知道每一层都有哪些节点。只需在每一轮循环开始时记录当前队列大小size然后连续弹出size个节点void levelOrderByLevel(TreeNode *root) { if (root nullptr) return; queueTreeNode* q; q.push(root); while (!q.empty()) { int size q.size(); for (int i 0; i size; i) { TreeNode *node q.front(); q.pop(); cout node-val ; if (node-left) q.push(node-left); if (node-right) q.push(node-right); } cout endl; } }输出结果A B C D E F这个 for 循环之所以可行是因为q.size()在循环开始时就被记录后续 push 进去的下一层节点不会干扰当前层的边界。利用这个写法配合一个计数器还能顺手求二叉树最大宽度、最大深度、判断是否完全二叉树。这些题目本质上都是在层序遍历骨架上做扩展。4.3 层序遍历的空间代价层序遍历的空间复杂度是 O(w)w 是树的最大宽度也就是某一层最多有多少个节点。满二叉树最后一层节点数是 n/2所以最坏情况下队列需要容纳约 n/2 个节点比递归版的 O(h) 大不少但依然在 O(n) 级别。在平衡树上h 远小于 w在极端斜树上w 又只有 1。实际选哪种取决于你是更怕栈溢出还是更怕内存开销。5. 三种遍历在真实工程里的用武之地5.1 前序序列化与结构重建前序遍历的根节点最先被记录这个特性让它特别适合做树的序列化。把一棵树按前序输出成字符串比如A B D # # E # # C # F # #其中 # 表示空节点之后就能用这个字符串完整复原出原来的树结构。反序列化时重建每一个根节点然后递归处理它的左右子树顺序和前序完全一致。很多网络通信和持久化场景都用这个思路把树形配置、目录结构、表达式树存成文件需要时再读回来。前序遍历的“自顶向下”特性还常用于复制一棵二叉树、查找某个节点等只需要访问根就能决策的操作。5.2 中序二叉搜索树的有序输出中序遍历在二叉搜索树BST上有一个非常漂亮的性质输出结果一定是从小到大的有序序列。因为 BST 的定义是左子树所有节点小于根右子树所有节点大于根而中序正好按“左 - 根 - 右”处理。void printSorted(TreeNode *root) { if (root nullptr) return; printSorted(root-left); cout root-val ; printSorted(root-right); }利用这个性质可以很方便地把 BST 转成有序数组、判断一棵树是不是 BST、查找第 k 小元素。判断 BST 时常见做法就是用中序遍历检查输出是否严格递增只要有一个位置违背递增关系整棵树就不是 BST。这个思路比直接在递归中比较当前节点和左右孩子更稳妥因为后者容易漏掉“左子树的所有节点都小于根”这个全局约束。5.3 后序自底向上的计算与资源释放后序是“先孩子后根”天然适合需要先处理子节点再处理父节点的场景。最典型的是删除整棵树你必须先释放左右子树的内存再释放根节点否则根都没了你就找不到孩子节点了。void deleteTree(TreeNode *root) { if (root nullptr) return; deleteTree(root-left); deleteTree(root-right); delete root; }同样的思想也可以套到计算目录大小上先递归计算所有子目录的大小再汇总到当前目录表达式求值也是先计算左右子树对应的子表达式再根据根节点的运算符做合并。后序遍历的工程价值本质上就是“自底向上的聚合”。面试里还有一个高频综合题给定一棵树的前序和中序遍历序列重建整棵树。思路是前序序列的第一个元素一定是根在中序序列里找到这个根的位置它的左边是左子树、右边是右子树然后递归处理左右两个区间。这类题目考察的就是你对两种遍历顺序的理解深度。5.4 一道综合题的思路用遍历结果重建二叉树具体来说假设前序序列是[A, B, D, E, C, F]中序序列是[D, B, E, A, C, F]。从前序知道根是 A在中序里 A 的下标为 3所以左子树中序区间是[D, B, E]长度 3右子树中序区间是[C, F]。前序序列里A 后面 3 个元素[B, D, E]属于左子树剩下的[C, F]属于右子树。递归继续左子树的根是 B右子树的根是 C最终就能还原整棵树。这类题的代码实现不复杂但非常考验你对“前序负责找根、中序负责分左右”这两个职责的清晰认知。6. 我写遍历代码时踩过的坑以及一套验证思路6.1 递归忘记判空导致段错误递归版本最容易犯的错就是忘记写if (root nullptr) return;。很多初学者觉得“一棵树不可能传空指针进来”但递归到叶子节点时root-left就是空的不先判空就会对 nullptr 解引用运行时直接段错误。我在给二叉树测试用例配数据时就经常遇到这种问题尤其是用数组手动构造树时最后一个空孩子的边界最容易漏。建议写递归函数的习惯是先写出口再写逻辑。出口条件就是当前节点为空直接 return这样后续代码才能安全使用root-left和root-right。6.2 迭代前序把左右压栈顺序写反前序迭代里的压栈顺序其实是“先右后左”很多同学一上来写成push(left)再push(right)结果输出变成了A C F B D E右子树整体跑到左子树前面。这个错误很隐蔽因为你可能只拿一棵很简单的树测试看不出问题一旦树变大顺序就会明显不对。我的记忆方法是栈是后进先出我想让左子树先出栈就必须让它后进栈所以先压右孩子再压左孩子。每次写迭代遍历都在心里默念一遍“出栈顺序 压栈逆序”能少踩很多坑。6.3 中序迭代更新指针的位置中序迭代最经典的错误是把内层while (cur ! nullptr)写成if (cur ! nullptr)结果只压入左孩子就继续处理没法一路走到最左下角输出顺序错得莫名其妙。另一个错误是在弹栈输出后忘记cur cur-right导致死循环栈弹空后 cur 还是空外层循环退出右子树完全没被处理。中序迭代的正确节奏是内层循环负责“向左走到黑”弹栈后立刻输出然后转向右子树。右孩子即使为空也没关系下一轮外层循环会通过弹栈回到上一层节点。这里最好不要写成if (cur-right) { cur cur-right; } else { ... }那样绕直接用cur cur-right更干净。6.4 后序双栈版的压栈顺序容易搞反双栈版第一个栈的作用是产生“根右左”的序列。为了先得到右孩子压栈时必须先压左孩子、再压右孩子。很多同学这里和前序迭代混淆一顺手就写反最后输出变成了A B D E C F和前序一模一样但显然不对因为后序的第一个输出应该是 D最左叶子。如果测试时发现后序输出的最后一个节点不是根节点 A那一定是双栈的压栈顺序出了问题。6.5 一套可靠的测试用例与验证方法写完遍历代码我建议用以下三组用例验证空树nullptr应该什么都不输出也不崩溃。单节点树只输出根节点。非平衡链式树比如每个节点只有右孩子1 - 2 - 3前序和中序都是1 2 3后序是3 2 1。用非平衡链式树特别能检验迭代版是否漏处理了哪一侧。如果链式树三种遍历输出都符合预期大部分逻辑问题已经能暴露出来再换一棵平衡树验证左中右的相对顺序基本就稳了。还有一个实用技巧写递归版和迭代版各一份跑同样的随机数据逐项比较输出是否一致。不一致就说明迭代版有逻辑错误。这个“双版本对拍”的思路我在做算法题时屡试不爽比人肉手推快得多。另外提一句上面所有代码里的树节点都是用new手动创建的实际项目里更建议用unique_ptr、shared_ptr或者对象池管理生命周期否则释放节点时容易漏 delete 造成内存泄漏。尤其是写后序删除整棵树的例子时别把delete root写到递归调用之前那是经典的悬空指针 bug。我自己在初学二叉树遍历时最受益的一件事就是把递归版和迭代版并排写在一起逐行对照。递归版三行核心代码迭代版十几行代码表面看差别很大本质却是同一个访问顺序、同一种栈思想。把“访问顺序”和“栈/队列的行为”对上号之后二叉树遍历就不再是一组需要死记硬背的模板了。