“三道遍历题我都背下来了但面试官一问 ‘为什么迭代写法是这样’ 我就卡壳。”这是我刷力扣LeetCode时最真实的感受。尤其是第145题——二叉树的后序遍历标签是“简单”但有一天我翻题解区发现问迭代写法的人远比想象中多。树这种结构天然适合递归所以很多人习惯性调一个递归就AC了根本没想过它会怎么和栈扯上关系可真到面试里面试官往往会追问一句如果树很深怎么办你能不用递归写出来吗这篇我打算把后序遍历彻底聊透。不光给你三种解法——递归、迭代、Morris也会告诉你这道题在力扣热题100里到底处在什么位置和后面那些“最大深度”“平衡二叉树”到底有什么血缘关系以及为什么你写二叉树程序的时候总是莫名其妙报运行时错误。如果你是刚开始刷力扣的选手或者被树类题折磨过的老哥这篇应该能给你省下不少绕弯的时间。1. 为什么后序遍历值得专门写一篇1.1 后序遍历在力扣题库中的位置力扣的二叉树题目体系里94题中序、144题前序、145题后序这三道题是所有树题的底气。你随便翻一个“树”标签下的热门题最后多半能归到这三种遍历的某个变体上。很多人刷题有个误区觉得遍历不是考点结果遇到“二叉树的最大深度”“二叉树的直径”这类题就发懵。其实这些题的核心骨架就是一个后序先把左子树的信息算完再把右子树的信息算完最后拿到根节点做汇总。我用一个比较直白的比喻前序遍历是“从上往下做决定”适合复制树、序列化树中序遍历是“和二叉搜索树纠缠”因为中序能把搜索树变成有序序列而后续遍历是“从下往上汇报”适合做那些需要子节点先给结果、父节点再拍板的计算。如果你能记住这句话后序的应用场景在你脑子里就会清晰很多。另外力扣的“后序遍历”这题也是周赛和面试题里的常客。简单说它不只是一道独立的题而是理解“自底向上遍历”的钥匙。我在刷周赛时遇到过不少题约束条件一条比一条严明明有递归思路却逼着你想迭代。那时候我才意识到遍历三兄弟真的不能只背一个递归版。1.2 后序和前中序最大的不同很多初学者觉得后序不就是“左右根”嘛把前序的代码改一下顺序就行。怎么说呢表面上确实这么回事但迭代写法会出卖你——后序和前序在迭代里的推导完全不是一个难度。前序遍历是“根左右”因为根先被处理所以你用一个栈先压右孩子再压左孩子弹出的时候根首先被访问后面直接顺着孩子往下走就行。后序遍历是“左右根”根必须在最后才被访问这意味着你把根压进栈里之后必须能“再回来一次”才能输出它。这个“再回来一次”的需求才是迭代后序真正绕人的地方。还有一种流传很广的说法“后序就是前序的逆序”。这句话要严谨地讲必须是“根-右-左”这种变体前序的反转而不是标准“根-左-右”前序的直接反转。我见过不少人用标准前序的迭代写出了反转版一跑发现顺序全乱然后就开始怀疑人生。所以你一开始就别背这种捷径老老实实把“根最后访问”这个本质抓住后面再看到什么奇怪写法都能绕回来。2. 三种标准解法递归、迭代、Morris2.1 递归解法最直观但别小看它递归版是这道题的“送分答案”代码短、思路清晰也是很多人的舒适区。我直接贴你一份可以直接跑的C版本class Solution { public: vectorint postorderTraversal(TreeNode* root) { vectorint res; dfs(root, res); return res; } void dfs(TreeNode* node, vectorint res) { if (!node) return; dfs(node-left, res); dfs(node-right, res); res.push_back(node-val); } };如果你更习惯Python也可以这样写class Solution: def postorderTraversal(self, root: Optional[TreeNode]) - List[int]: res [] def dfs(node): if not node: return dfs(node.left) dfs(node.right) res.append(node.val) dfs(root) return res写递归的时候有件事特别重要先确定递归三要素——终止条件、单层逻辑、返回值。这里的终止条件是“节点为空”单层逻辑是“左、右、根”。我见过不少报错都是因为漏了对空指针的判断或者在空节点上直接访问val。比如写成if (node-val) return;这种离谱操作迟早翻车。另外一个没写在教科书里的问题递归在极端情况下会爆栈。如果一棵二叉树退化成一个链每个节点只有一个右孩子那么递归深度就是N。当N很大比如十万、百万级别的时候程序直接栈溢出力扣上表现就是“运行时错误”。所以面试官才会追着问“不用递归怎么写”他赌的就是你只会递归。2.2 迭代解法先绕开两种典型的坑后序的迭代写法大体分两派一派是“标记法”一派是“纯栈法”。我的建议是先把标记法学明白因为它最不容易出错而且能迁移到前序和中序。标记法的核心思路很直白栈里存的不是节点而是“这个节点以及它的访问状态”。第一次碰到节点时标记为“还没访问完”等它的左右子树都处理完了第二次再碰到它才输出它的值。用C写出来是这样class Solution { public: vectorint postorderTraversal(TreeNode* root) { vectorint res; if (!root) return res; stackpairTreeNode*, bool st; st.push({root, false}); while (!st.empty()) { auto [node, visited] st.top(); st.pop(); if (visited) { res.push_back(node-val); } else { // 后序左-右-根所以把根标记为已访问再压右、左 st.push({node, true}); if (node-right) st.push({node-right, false}); if (node-left) st.push({node-left, false}); } } return res; } };注意压栈顺序先把“根标记为待输出”压进去然后压右孩子最后压左孩子。因为栈是后进先出所以左孩子会先被弹出处理接着是右孩子最后才是轮到那个被标记为true的根节点。这个顺序和后序“左-右-根”完全一致。如果你不喜欢用pair还可以用纯栈加pre指针的写法规避掉状态标记。这个写法的核心是用一个pre指针记录上一次访问的节点。只有当“当前节点的右孩子为空”或者“右孩子已经访问过了”才说明左右子树都搞定了可以输出当前节点。否则就得先去处理右子树。class Solution { public: vectorint postorderTraversal(TreeNode* root) { vectorint res; stackTreeNode* st; TreeNode* cur root; TreeNode* pre nullptr; while (cur || !st.empty()) { while (cur) { st.push(cur); cur cur-left; } cur st.top(); if (cur-right cur-right ! pre) { cur cur-right; } else { res.push_back(cur-val); st.pop(); pre cur; cur nullptr; } } return res; } };这个版本的最大坑就是pre的更新时机。如果pre更新晚了你会发现同一棵右子树又被压进去一遍然后程序死循环。我的建议是拿一棵只有三个节点的树——根节点、左孩子、右孩子——手动把栈的每一步变化画出来。画一次之后对pre为什么这么设计会清楚很多。2.3 Morris解法O(1)空间但思路要绕一下递归和迭代的空间复杂度最好也只能做到O(h)h是树高最坏情况是O(n)。而Morris遍历能把这个空间压到O(1)它靠的是“线索化”利用节点原本为空的right指针临时指向某个后继节点等遍历完再把树还原。后序的Morris比中序Morris麻烦不少。官方题解里有个经典做法造一个虚拟节点把它的左孩子指向root然后按类似中序Morris的流程走同时配合一个“逆序输出右边界”的小技巧。伪代码大致是这样class Solution { public: vectorint postorderTraversal(TreeNode* root) { vectorint res; TreeNode* dummy new TreeNode(-1); dummy-left root; TreeNode* cur dummy; while (cur) { if (cur-left) { // 找左子树的最右节点也就是中序前驱 TreeNode* pre cur-left; while (pre-right pre-right ! cur) { pre pre-right; } if (!pre-right) { // 第一次到达建立线索继续往左走 pre-right cur; cur cur-left; } else { // 第二次到达撤销线索输出左子树的右边界 pre-right nullptr; reverseAdd(cur-left, res); cur cur-right; } } else { cur cur-right; } } delete dummy; return res; } private: void reverseAdd(TreeNode* node, vectorint res) { vectorint tmp; while (node) { tmp.push_back(node-val); node node-right; } reverse(tmp.begin(), tmp.end()); res.insert(res.end(), tmp.begin(), tmp.end()); } };这个代码的正确性可以信力扣题解但我不建议第一次学后序就从Morris入手。Morris更适合做“加分项”用来展示你对空间复杂度和线索化都有理解。这里唯一的担心是你在面试现场把二叉树的临时结构改了又还原如果其中一步出错整棵树当场就乱了。我的建议是如果你要用Morris一定提前把撤销线索的步骤背熟并且在纸上画一遍流程。2.4 三种解法放在一起对比解法时间复杂度空间复杂度是否修改二叉树主要易错点递归O(n)O(h)最坏O(n)否空节点判断、递归深度过大的栈溢出迭代-标记法O(n)O(n)否标记状态与压栈顺序不一致迭代-纯栈法O(n)O(h)否pre指针更新时机错误导致死循环MorrisO(n)O(1)是结束后还原前驱查找、逆序输出右边界四种方法没有绝对好坏要看场景。刷题时AC没问题但面试里被追问“空间能再优化吗”、项目中树特别深、或者你被明确要求不能破坏树结构时解法选择就变得很微妙。3. 力扣刷题实操经验从AC到真正会用3.1 先别急着划走AC以后问自己三个问题很多人刷题有个习惯一遍递归通过看到绿色打勾立刻切下一题。这个习惯不是不好而是会漏掉后序这道题最值钱的部分——迭代写法。我自己的习惯是第一遍用递归AC之后会强制自己再写两个版本如果这棵树有十万个节点我的递归会不会爆栈我能不能用栈实现完全相同的结果我能不能在三天后不看任何题解重新写出这套逻辑这三个问题逼着我把“背代码”升级成“理解过程”。特别是后序的迭代我至少重写了三遍才终于不再怀疑pre指针的更新位置。分享一个我实际踩过的坑第一次写纯栈版本的时候我照着一个模板敲里面判断条件是if (cur-right pre ! cur-right)我当时想当然把pre初始化为root结果第一轮循环就死循环了。后来把每个变量的变化都列出来才发现pre必须从空开始因为它代表的是“上一次已经处理完的节点”而不是“上一次进入循环的节点”。这种经验不太可能写在官方题解里但你自己踩一次比看十遍注释都管用。3.2 热题100里的后序变体其实都是同一套思路很多人在热题100里边刷边忘就是因为每道题都当成孤立的题来记。其实把后序理解透了一道题能带出一串题。比如“二叉树的最大深度”你只需要在后序遍历的基础上取左右子树的较大值加一。核心代码就是int maxDepth(TreeNode* root) { if (!root) return 0; int left maxDepth(root-left); int right maxDepth(root-right); return max(left, right) 1; }再看“平衡二叉树”判断左右子树高度差是否超过1这同样是后序先拿左右子树高度再比较。如果子树已经不平衡返回一个特殊标记比如-1。“二叉树的直径”也一样只不过多了一个全局变量用来在递归过程中不断更新最大值。你会发现所谓热题100里的树题不是二叉树遍历的“反套路”而是后序的“套娃”。把后序这个母题吃透其他题目就都是在加东西加一个全局变量、加一个前缀和、加一个HashMap。我自己在整理题解时甚至会把这些题的入口代码统一改成后序递归框架然后只改中间的“汇总逻辑”这样一段时间后脑子里的结构会非常清晰。3.3 关于刷题顺序和节奏的建议很多刚刷力扣的朋友一上来就开始100题刷到树就卡住然后又回去看视频来回折腾。我的建议是树这类的题最适合“集中刷”第一步把94、144、145三道遍历题刷完做到递归版、迭代版随手就能写。第二步去刷104最大深度、110平衡二叉树、543直径、226翻转二叉树这类题都是遍历的简单加工。第三步每周参加一次周赛只求把前两题做出来重点训练限时下的思路切换能力。这个路径我实测过能帮你把“二叉树遍历”从一个抽象概念变成一件顺手的事。特别提醒周赛里经常有一些题不会直接告诉你“用后序”但它要求自底向上处理信息这时候你如果能识别出后序的骨架解题速度会明显快于现场推栈。4. 写二叉树程序时为什么总是报运行时错误4.1 三类最常见的运行时错误先说结论力扣上报运行时错误十有八九和空指针有关。我有一次写后序非要在递归里写if (node-left nullptr node-right nullptr)这本身没问题但如果中间某次递归把空节点传进来了下一层直接访问“空节点的左孩子”当场起飞。所以第一条铁律是在二叉树里访问任何成员之前先确认它不为空。第二类是栈溢出。树如果退化成一条链递归深度就变成O(n)。力扣的测试环境对栈空间并不宽松尤其在一些边界测试里会卡得很明显。这类错误的特点很烦人本地小数据跑得好好的一提交就崩。应对方案也很简单——改迭代。第三类是死循环多出现在迭代或者Morris里。比如忘了在遍历之后撤销线索线索一直存在第二次访问同一个节点时找不到正确的出口程序就在那一直转圈。死循环比空指针更隐蔽因为普通逻辑也很难一眼看出。4.2 力扣报错信息的阅读姿势力扣的报错信息其实很有温度只是很多人看到英文就略过了。比如member access within null pointer of type TreeNode这个英文说的就是“在空指针上访问了成员”基本等于告诉你某个节点是空但你还在找它的左孩子或者右孩子。看到这种报错第一反应是检查所有访问node-left、node-right、node-val的地方看看前面有没有判空。再比如这种AddressSanitizer: stack-buffer-overflow别慌这是内存越界。常见于数组访问越界或者栈相关的访问越界和“递归爆栈”是两回事。如果是C选手还经常遇到reference binding to null pointer这个多是访问了空vector或者空指针引用的元素。我自己排查这类问题的方式是先把输入树打印出来再在关键逻辑里加几个输出语句看它到底在哪一步触发了空访问。4.3 本地调试用什么输入力扣的测试输入是层序数组但本地调试的时候这个格式并不方便。我建议你在本地写一个简单的测试树直接用指针把节点串起来TreeNode* root new TreeNode(1); root-left new TreeNode(2); root-right new TreeNode(3); root-left-left new TreeNode(4); root-left-right new TreeNode(5);这棵树虽然小但足够验证四种顺序4、5、2、3、1是后序。你完全可以拿它来手动模拟栈的变化。想测边界就单独测空树nullptr、单节点树、链状树。把这四种测试树建好之后绝大多数运行时错误都能在本地复现。4.4 常见问题速查表报错表现最常见原因排查思路空节点访问成员没判空就访问node-left/right/val在关键位置打印节点状态检查指针是否为空栈溢出/递归深度过大二叉树退化为链、递归无终止条件改用迭代人工限制输入规模死循环迭代中pre更新错误、Morris线索未撤销打印循环中的节点顺序重点看栈的变化结果顺序错乱压栈顺序和输出顺序不一致手动模拟一个三层树的栈过程本地正常、OJ报错力扣有大数据边界测试用链状树、空树、单节点树自测5. 遍历二叉树能做什么从自底向上到真实场景5.1 后序在系统和底层库里的应用后序不只是算法题它广泛存在于真实系统中。最典型的例子是统计目录大小你想知道一个文件夹占了多少磁盘空间必须先递归统计所有子文件夹再把它们加起来最后加上当前目录的文件大小。这个流程天然是后序。表达式求值也是一个经典场景。编译器把表达式解析成表达式树后要对它求值就得先算叶子节点的值再算运算符节点的结果。后序遍历得到的序列其实就是后缀表达式很多解释器和计算器用到的核心数据结构都与它有关。还有内存/对象释放里的“先释放孩子再释放父亲”这也是后序。父节点持有子节点的引用如果你先释放父节点可能连访问子节点的入口都没了所以要反过来操作。5.2 热词里的“超市货架 遍历二叉树”有次看到有人拿超市货架比喻二叉树我觉得特别贴切。整个超市是根节点每个大品类是枝干具体商品是叶子。如果你要统计某个大品类的总库存金额不可能直接读大品类的数字得先把每个单品的价格加起来再汇总到子类再汇总到品类。这就是后序遍历的现实版本。如果你要做的是一个商品目录树从上往下打印大类、子类、商品那又是前序遍历。你会发现遍历顺序本质上决定了“信息的流动方向”。这个比喻用来给非技术朋友讲算法特别方便自己用也很有画面感。5.3 线索二叉树和Morris的关系热词里还有一个“线索二叉树”。这个东西和Morris遍历的关系很微妙线索二叉树的思想是把二叉树的空指针充分利用起来让right指针指向中序后继left指针指向中序前驱这样遍历时可以免去递归或栈。Morris遍历的灵感恰恰来自线索化但它不显式新建线索字段只是临时借用节点原本为空的right指针作为“返回路径”遍历完成后又恢复原样。理解了线索二叉树再回头看Morris的代码你就不会觉得它是在变魔法而是“在线索化和还原之间反复横跳”。我个人体会后序Morris比中序难懂是因为后序本身多了一个“逆序输出右边界”的操作这相当于在Morris基础上又叠加了一个链表反转。如果你没有先把链表反转练熟直接上后序Morris会非常痛苦。所以我的建议是先用中序Morris把线索化思想吃透再回来挑战后序会顺手得多。关于后序遍历最后再补一句我踩过几次坑之后的经验刷题的时候代码能跑通只是第一层真正有用的是你能不能用语言把“为什么这样压栈、为什么这样更新指针”讲清楚。面试官往往不会只盯着AC他更想看到你脑子里有没有那棵“栈的变化图”。如果你也在迭代写法上卡过壳不妨找一张纸把一个三层树从头到尾模拟一遍写到能把每一步说给自己听为止。那之后你会发现不只是后序整个二叉树的题感都会上一个台阶。