我最早学二叉树遍历的时候把“前序根左右、中序左根右、后序左右根”背得滚瓜烂熟结果第一次手写非递归后序直接翻车。后来才想明白一件事递归版和非递归版之间差的不是“把递归换成循环”而是你对函数调用栈的理解深度。这篇文章就用一棵具体的树把二叉树的三种遍历从递归讲到非递归把每一步为什么这么写都拆开揉碎。不管你是刚接触树的初学者还是面试前想系统复习一遍的开发者这篇文章都能让你把这块硬骨头彻底啃下来。1. 先看调用栈三种遍历共用同一个骨架1.1 递归背后的“系统栈”很多人递归版写得很顺一换非递归就卡住根本原因是对递归的理解停留在“函数会自己把自己调明白”。实际上递归不是魔法它背后是系统维护的一张调用栈每次函数调用都会把参数、局部变量和返回地址压入栈中函数返回时再弹出。拿前序遍历举例当你写下preorder(root-left)这行代码时当前节点的现场被压栈然后带着左孩子进入新一层调用。左子树全部处理完毕才弹栈回到原来的节点继续走preorder(root-right)。这个“压栈—进入子树—弹栈—返回”的过程就是三种遍历共同的底层骨架。非递归实现本质上就是手动维护这张栈只是不再有函数调用的开销和栈溢出的风险。1.2 用一个例子把三种顺序刻进脑子后面所有章节都用同一棵树来演示方便对照1 / \ 2 3 / \ \ 4 5 6三种遍历对应的输出是遍历方式输出序列前序遍历1 2 4 5 3 6中序遍历4 2 5 1 3 6后序遍历4 5 2 6 3 1这三个序列怎么来的关键在于“访问当前节点”这个动作发生在递归调用的哪个位置发生在进入左子树之前就是前序发生在左子树返回之后、右子树进入之前就是中序发生在左右子树都返回之后就是后序。所以三种递归遍历的代码结构完全相同唯一不同是visit(cur)这一行代码的位置。2. 递归遍历移动一行代码改变整棵树的访问节奏2.1 前序先动手再分工前序遍历的顺序是“根—左—右”对应到生活场景就是接到一个任务先自己处理掉最核心的部分然后把剩下的拆成左右两个子任务交给别人子任务内部再按同样的规则继续拆解。用上面的树走一遍前序先访问根节点 1然后进入左子树 2访问 2再进入它的左子树 4访问 4发现没有孩子返回上一层再进入 2 的右子树 5访问 5返回再回到根节点 1进入右子树 3访问 3再进入 3 的右子树 6访问 6结束。整个路径是沿着左边界一路向下访问遇到左孩子为空就回溯到最近的未访问右子树。这个顺序在复制一棵树、对树做序列化时特别有用因为根总是先于子树出现重建时可以直接确定根节点。2.2 中序把左半场处理完再回来中序遍历的顺序是“左—根—右”它的特点是当一个节点被访问时它的左子树一定已经全部处理完毕。这就是为什么对二叉搜索树做中序遍历得到的结果一定是有序序列——因为 BST 的左子树所有节点都小于根右子树所有节点都大于根中序天然把大小关系排列出来。用样例树走中序从根节点 1 出发先一路向左走到 44 没有左孩子访问 4返回到 2访问 2再进入 2 的右子树 5访问 5返回 1访问 1进入右子树 3一路左走到空访问 3再进入 6访问 6。最后的序列是 4 2 5 1 3 6。如果你需要在 BST 上求第 K 小元素、验证一棵树是不是 BST或者把 BST 转成有序数组中序遍历都是最直接的思路。2.3 后序先把子问题全部兑现后序遍历的顺序是“左—右—根”也就是说一个节点必须等左右子树全部处理完最后才访问自己。列一个形象的比喻你是团队负责人汇报顺序是让小组成员先汇报各自负责的部分等你收集完所有信息后再向你的上级做整体汇报。样例树的后序是 4 5 2 6 3 1先处理 1 的左子树 2而 2 又要先处理它的左子树 4 和右子树 5左半场全部结束访问 2再处理 1 的右子树 33 要先处理右子树 6全部回来之后最后访问 1。后序最经典的应用是“从下往上”的计算比如表达式树求值要先算左右孩子的结果再算父节点或者删除整棵二叉树时需要先删光孩子节点再删当前节点不然先把父节点删了子节点就再也找不到了。2.4 递归版代码与时空复杂度递归版代码可以说是二叉树遍历最简洁的形态。先定义节点结构struct TreeNode { int val; TreeNode *left, *right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} };三种递归实现如下// 前序根 左 右 void preorder(TreeNode* root) { if (!root) return; cout root-val ; preorder(root-left); preorder(root-right); } // 中序左 根 右 void inorder(TreeNode* root) { if (!root) return; inorder(root-left); cout root-val ; inorder(root-right); } // 后序左 右 根 void postorder(TreeNode* root) { if (!root) return; postorder(root-left); postorder(root-right); cout root-val ; }三个函数连结构都完全相同只有cout这一行的位置不同。时间复杂度都是 O(n)因为每个节点恰好被访问一次。空间复杂度看的是递归调用栈的最大深度也就是树高 h平衡树是 O(log n)链状树会退化到 O(n)。这一点很关键后面讲递归栈溢出的时候还会再提到。3. 非递归前序与中序手撕调用栈的两种节奏3.1 前序的迭代法弹出根节点后先压右、再压左非递归前序是所有迭代版里最好写的思路就是手动重现系统栈的行为先把根节点压栈循环弹出栈顶节点并访问然后把它的右孩子、左孩子依次压栈。为什么是先压右再压左因为栈是后进先出后压进去的左孩子会先被弹出。只有先处理右子树入栈、再把左子树放上去才能保证左孩子先出栈从而保持“根—左—右”的顺序。这段逻辑用代码写出来void preorderIter(TreeNode* root) { if (!root) return; stackTreeNode* st; st.push(root); while (!st.empty()) { TreeNode* cur st.top(); st.pop(); cout cur-val ; if (cur-right) st.push(cur-right); if (cur-left) st.push(cur-left); } }还是用样例树走一遍弹出 1 访问压入 3、2弹出 2 访问压入 5、4弹出 4 访问弹出 5 访问弹出 3 访问压入 6弹出 6 访问。得到了 1 2 4 5 3 6和递归版完全一致。写这个版本时最容易犯的错误是把压栈顺序写反一旦先压左再压右输出会变成“根—右—左”也就是一种镜像的前序遍历后面后序的双栈法恰恰会故意利用这个特性。3.2 中序的迭代法一路向左弹栈转向中序迭代比前序多了一点思考量核心策略是“能往左就往左走不动了才弹栈”。为什么因为中序要求左子树先访问所以从根开始要先把所有左孩子一路压进栈直到某个节点没有左孩子为止。此时栈顶是最左侧的节点弹出访问然后转向它的右子树再重复“一路向左”的过程。void inorderIter(TreeNode* root) { stackTreeNode* st; TreeNode* cur root; while (cur || !st.empty()) { while (cur) { st.push(cur); cur cur-left; } cur st.top(); st.pop(); cout cur-val ; cur cur-right; } }最容易漏掉的一行代码是cur cur-right。如果没有这一行弹出左子树节点并访问后外层循环再次进入内层while又会从同一个节点开始一路向左形成死循环。cur cur-right的意思是左子树和中节点都处理完了接下来把右子树当作一棵独立的树重新执行整个算法。对着样例树推一遍就能看到中序迭代就是沿着“左边界下钻、弹栈访问、转向右子树”三个动作反复循环。3.3 边界条件与两种迭代法的坑写非递归版本时边界条件比递归更容易翻车。最关键的是空树处理前序直接在开头if (!root) return中序则要在循环条件里带上cur || !st.empty()否则空树无法进入逻辑。很多初学阶段的中序代码写成while (!st.empty())然后把root直接拿来用空树时就会在开头报错。另一个容易被忽略的点是退化树。如果一棵树只有右孩子不管递归还是非递归辅助空间都会退化到 O(n)。我在调试一个极端的单链树时统计过栈的增长压栈次数恰好等于节点总数这提醒我们非递归版本解决了“函数调用栈溢出”的问题但并没有把空间复杂度本身降下来。真正想把空间压到 O(1) 的只有后面要介绍的 Morris 遍历。4. 非递归后序双栈法、状态标记法和指针法4.1 双栈法用“根右左”逆序拼出“左右根”后序是非递归遍历里最折磨人的一个因为“根”是最后访问的而栈天然适合“先进后出”的逆序处理。双栈法换了个角度思考后序是“左—右—根”把它逆序看就是“根—右—左”。“根—右—左”恰恰是一种镜像的前序遍历访问根先处理右子树再处理左子树。我们可以先按“根右左”的顺序遍历整棵树把结果按顺序压进第二个栈最后再从第二个栈里依次弹出得到的就是“左右根”。void postorderTwoStacks(TreeNode* root) { if (!root) return; stackTreeNode* s1, s2; s1.push(root); while (!s1.empty()) { TreeNode* cur s1.top(); s1.pop(); s2.push(cur); if (cur-left) s1.push(cur-left); if (cur-right) s1.push(cur-right); } while (!s2.empty()) { cout s2.top()-val ; s2.pop(); } }为什么这里压栈顺序变成了先压左、再压右因为s1弹出的顺序决定了“根右左”的生成顺序后压进去的右孩子会先弹出于是先处理右子树再处理左子树。每个从s1弹出的节点都被压进s2最后s2的栈顶到栈底恰好是“左右根”的反向关系弹出即得后序序列。4.2 状态标记法给每个节点打上“孩子处理完了吗”双栈法很好理解但在某些要求“只能用一个辅助栈”的场合还需要另一种思路状态标记法。它的核心思想是模拟递归的完整过程给每个节点标记一个状态记录“这个节点的左右子树是否都已经处理完毕”。不直接压节点本身而是压一个包装结构里面带上布尔标记struct Frame { TreeNode* node; bool visited; }; void postorderState(TreeNode* root) { if (!root) return; stackFrame st; st.push({root, false}); while (!st.empty()) { Frame f st.top(); st.pop(); TreeNode* cur f.node; if (!cur) continue; if (!f.visited) { st.push({cur, true}); if (cur-right) st.push({cur-right, false}); if (cur-left) st.push({cur-left, false}); } else { cout cur-val ; } } }第一次遇到某个节点时visited为 false此时不访问而是把标记为 true 的当前节点压回去再把右孩子、左孩子按序压栈。因为栈是后进先出左孩子最后压入所以它最先被弹出处理左子树处理完再处理右子树最后弹出标记为 true 的当前节点这时候才真正访问它。这个方法和递归的流程几乎一一对应初学阶段强烈推荐用这种写法理解后序的“延迟访问”。4.3 指针法lastVisited怎么判断右子树已访问状态标记法直观但每个节点都要额外携带一个布尔量。更极致的单栈写法用一个指针记录“上一次访问的节点”判断右子树是否已经处理完。核心逻辑是当栈顶节点有右孩子并且右孩子不是上一次访问的节点时说明右子树还没处理先把指针转向右孩子继续压栈否则说明左右子树都已经结束可以弹出访问当前节点。void postorderPointer(TreeNode* root) { stackTreeNode* st; TreeNode* cur root; TreeNode* last nullptr; while (cur || !st.empty()) { if (cur) { st.push(cur); cur cur-left; } else { TreeNode* top st.top(); if (top-right last ! top-right) { cur top-right; } else { cout top-val ; last top; st.pop(); } } } }这个写法理解起来有个坎为什么只要比较last ! top-right就够了因为后序遍历在访问完一个节点的右子树后会立刻访问这个节点本身而右子树里最后被访问的节点恰好就是右子树的根节点。所以当上一次访问的节点正好等于当前节点的右孩子时可以确定右子树已经全部处理完是时候弹出当前节点了。这个技巧很巧妙但新手容易忘记更新last编码时要注意。4.4 三种后序迭代法怎么选三种方法各有优劣做笔试做题和写工程代码的取舍不太一样我通常这样建议方法额外空间是否易错推荐场景双栈法O(n)不易错笔试快速写出正确解状态标记法O(n)思路清晰面试时讲清楚递归语义lastVisited 指针法O(n)条件容易漏追求单栈实现的场景时间都是 O(n)额外空间在最坏情况下也都是 O(n)。双栈法代码最省心状态标记法面试时最好讲lastVisited 指针法则适合用来展示你对后序访问时机的理解深度。5. 一套通杀三种遍历的统一模板nullptr哨兵法5.1 哨兵法为什么能通杀前序、中序、后序的迭代法各有各的写法记忆负担很重。实际上有一个非常优雅的统一模板核心是在栈里插入一个nullptr哨兵用它标记“当前节点的孩子都处理完了下一次弹出时应当访问当前节点”。理解了这个思想三套代码只需要挪动三行的位置。为什么哨兵能起作用因为普通节点表示“这是一棵待处理的子树”而nullptr表示“下一个要处理的不是子树而是真正的访问动作”。弹出nullptr时栈顶必然是某个节点弹出并访问它即可。这等于把递归中“从子调用返回后继续执行”的动作显式地编码进了栈里。5.2 三套模板只要挪三行先看前序。前序要求“根—左—右”所以访问动作应该发生在处理左右子树之前。入栈时因为栈是后进先出要让左子树先被处理就把右子树先压栈再压左子树然后把当前节点和nullptr压在最后保证下一轮首先弹出nullptr并访问当前节点void preorderUnified(TreeNode* root) { if (!root) return; stackTreeNode* st; st.push(root); while (!st.empty()) { TreeNode* cur st.top(); st.pop(); if (cur ! nullptr) { if (cur-right) st.push(cur-right); if (cur-left) st.push(cur-left); st.push(cur); st.push(nullptr); } else { cout st.top()-val ; st.pop(); } } }中序要求“左—根—右”入栈顺序调整成右孩子、当前节点、nullptr、左孩子。这样左孩子会在最上层先被处理左子树完全结束之后nullptr才会带着当前节点浮到栈顶完成访问void inorderUnified(TreeNode* root) { if (!root) return; stackTreeNode* st; st.push(root); while (!st.empty()) { TreeNode* cur st.top(); st.pop(); if (cur ! nullptr) { if (cur-right) st.push(cur-right); st.push(cur); st.push(nullptr); if (cur-left) st.push(cur-left); } else { cout st.top()-val ; st.pop(); } } }后序要求“左—右—根”所以当前节点必须最晚被访问。入栈顺序是当前节点、nullptr、右孩子、左孩子。左右子树会被依次处理等它们都结束nullptr才出现访问当前节点void postorderUnified(TreeNode* root) { if (!root) return; stackTreeNode* st; st.push(root); while (!st.empty()) { TreeNode* cur st.top(); st.pop(); if (cur ! nullptr) { st.push(cur); st.push(nullptr); if (cur-right) st.push(cur-right); if (cur-left) st.push(cur-left); } else { cout st.top()-val ; st.pop(); } } }有没有发现规律其实只需要记住一个原则你想让“访问当前节点”这个动作排在什么时候就把nullptr插在对应位置。前序中左右孩子都还没压栈就先放标记所以根最先被访问中序把标记放在左右孩子之间所以根在左子树之后、右子树之前被访问后序把标记放在左右孩子都压完之后所以根最后被访问。5.3 统一模板的实际效果检验用样例树验证后序统一模板初始压入 1弹出 1 后栈中从底到顶是cur1, nullptr, right3, left2弹出left2后继续展开2的子树会让4、5先处理处理完 4 和 5 后栈顶变成cur2前的nullptr于是访问 2再处理 3 和 6最后访问 1。输出为 4 5 2 6 3 1完全正确。这个模板的缺点是栈里会混入空指针严格来说辅助空间会比正常迭代法多出 O(n) 的空标记但在实际刷题和面试手写中完全可接受。它的最大优势是你不需要为后序单独记一套双栈逻辑一套模板解决三种遍历写错概率大幅下降。6. 进阶与避坑Morris遍历、递归深度与实战选择6.1 Morris遍历把空间压到O(1)的线索思想前面所有迭代版的空间复杂度都是 O(h)因为辅助栈的深度和树高挂钩。Morris 遍历则用了一招非常聪明的“线索化”利用叶子节点原本为空的右指针临时指向它的中序后继节点遍历结束后再恢复现场。这样整个过程不需要任何栈空间做到 O(1)。以中序举例。当前节点记为cur如果它没有左子树直接访问cur并向右走如果有左子树就找到左子树的最右节点这个节点是cur在中序下的直接前驱。如果前驱的右指针为空就把右指针临时指向cur然后进入左子树如果前驱的右指针已经指向cur说明左子树已经遍历完此时恢复前驱的右指针为空访问cur再转向右子树。代码可以写成void morrisInorder(TreeNode* root) { TreeNode* cur root; while (cur) { if (!cur-left) { cout cur-val ; cur cur-right; } else { TreeNode* pred cur-left; while (pred-right pred-right ! cur) { pred pred-right; } if (!pred-right) { pred-right cur; cur cur-left; } else { pred-right nullptr; cout cur-val ; cur cur-right; } } } }Morris 前序和后序也都能做后序稍微更绕一些。老实说我只有在面试被明确问到“O(1) 空间遍历二叉树”时才会用 Morris日常刷题犯不着自找麻烦。理解它的意义在于知道“遍历二叉树并没有把空间压到 O(1) 以外的理论极限”而不是每个题都套它。6.2 链状树和递归栈溢出递归版写起来最爽但它有个隐藏的雷递归深度等于树高而不是节点数。普通业务里二叉树比较平衡深度几十层没问题可一旦输入退化成一棵只有右子树的链状树1 万层可能直接击穿调用栈。我在一次压测中遇到过类似情况数据是从排序好的数组直接构建的二叉搜索树结构变成了单链递归中序遍历跑到几千层就抛异常。改成非递归版之后进程就稳定了。这件事给我的教训是只要树的形态不受控优先考虑迭代版就算面试时写递归也要主动和面试官说明深度风险。还有一个小提醒递归栈溢出和堆内存不足是两回事。递归用的是进程栈默认空间通常只有几 MB而辅助栈用的是堆容量大得多。这也是为什么要用“显式栈模拟递归”来解决深层树问题的原因。6.3 三种遍历在真实题目里的应用学遍历不能只停留在“会输出序列”要把它当成解题的基本武器库。中序遍历的第一反应是二叉搜索树有序化求第 K 小节点、验证 BST、找两个节点的错误位置全是中序的活。前序遍历的价值在于“拷贝”和“重建”因为根节点最先出现复制一棵树时可以先创建根再递归创建左右子树。序列化二叉树时前序配合空节点标记是最容易实现的一种方案。后序遍历则适合一切“先处理孩子、再处理父亲”的题目表达式树求值需要先算左右孩子的值才能算当前节点统计子树信息并向上汇总是“树形动态规划”的典型写法删除二叉树必须先删左右孩子再删根不然孩子节点会永远丢失。选遍历方式时先问自己我需要先知道哪个节点的信息才能处理当前节点6.4 我的记忆口诀与最后提醒如果只想记一套口诀我建议这样记递归看cout位置前序迭代记住“根弹出先右后左入栈”中序迭代记住“一路向左弹栈向右”后序迭代最快上手的就是双栈法或者统一模板里“把nullptr的位置当成访问时机”。统一模板你只要能背住一套就能推出三套。最后送一个我自己试过很多次的小方法别对着代码死记硬背拿一棵有三个以上节点的树把入栈、出栈、访问的每一步都写在纸上连续推三遍。每一步都写得清清楚楚之后你对这三种遍历的理解就不再是“背顺序”而是真正看懂了它们如何用栈结构控制访问时机。这一步跨过去后续遇到任何树的题目都会顺手很多。