★ FEATURED ARTICLE 坚持刷题刷到第38天今天轮到了LeetCode第145题二叉树的后序遍历。二叉树的遍历题目里前序和中序的迭代写法大多数人都能很快搞定但后序的迭代实现却经常让人卡壳——不是结果顺序错乱就是写成了前序的变体要么就是死循环。这篇文章把我从“递归秒写”到“迭代翻车”再到把三种迭代思路彻底吃透的完整过程整理出来尤其适合正在刷二叉树专题、被“后序迭代”虐过的同学。二叉树的遍历是很多算法题的基石后序遍历本身也常和树的深度计算、删除节点、表达式求值这类实际问题挂钩。这篇不会只贴代码我会把每一种写法的思考路径、入栈顺序、为什么这样设计都拆开讲清楚再附上我实际调试时遇到的报错和排查方法。1. 先搞懂后序遍历本身递归模板为什么显得简单1.1 后序遍历的访问顺序到底特殊在哪后序遍历的顺序是“左子树 - 右子树 - 根节点”也就是先处理完左右两个孩子最后才轮到当前节点。拿一棵具体的树举例1 / \ 2 3 / \ \ 4 5 6这棵树的后序遍历结果是4, 5, 2, 6, 3, 1。注意根节点1是最后一个输出的左子树的三个节点4, 5, 2、右子树的四个节点6, 3都先于根节点输出。很多人不理解这个顺序的意义我举个生活化例子后序遍历就像你去一个公司拜访领导但领导架子大规定你必须先把他手下的所有员工都见完最后才轮到他。于是你的路线就是先走左边办公区见完所有基层员工再走右边办公区见完另一拨员工最后回到领导办公室盖章。这个“最后盖章”的动作就是输出根节点。1.2 递归三要素参数、终止条件、单层逻辑写递归前先想清楚三件事递归函数的参数和返回值是什么终止条件是什么单层递归的逻辑是什么在后序遍历这道题里递归函数接收一个TreeNode节点和一个结果列表返回值是void因为我们是把遍历结果累加到列表里。终止条件是当前节点为空直接返回。单层逻辑就是“先递归左子树再递归右子树最后把当前节点的值加入结果”。class Solution { public ListInteger postorderTraversal(TreeNode root) { ListInteger result new ArrayList(); postorder(root, result); return result; } private void postorder(TreeNode root, ListInteger result) { if (root null) { return; } postorder(root.left, result); postorder(root.right, result); result.add(root.val); } }核心代码就三行看起来简单到不行。但这里面藏着一个关键点为什么终止条件是root null就够了因为叶子节点的左右孩子都是null递归到空节点时返回就不会出现空指针异常。这也顺带解释了为什么很多人写的二叉树程序总是报运行时错误——八成是某个方法入口没有判空或者递归里少了终止条件。1.3 手动模拟递归调用栈人脑栈最容易记乱递归写起来快但理解起来有个坎系统帮你维护了一个调用栈每次递归调用一个函数都会把当前的状态压栈等子调用返回后再恢复。以这棵树为例调用postorder(1)时系统先记住“我现在在节点1”然后调用postorder(2)进入postorder(2)后记住“在节点2”继续调postorder(4)……这一路“记住”的动作就是压栈。等postorder(4)返回后才轮到执行result.add(2.val)。很多人递归写不对就是把“先递归再输出”的顺序搞反了手一抖把result.add(root.val)写到了最前面结果变成了前序遍历。所以写递归时一定要把“单层逻辑的先后顺序”和“遍历顺序”严格对应起来。2. 迭代实现的三条路线为什么后序迭代比前序麻烦2.1 不能照搬前序遍历的迭代模板先看前序迭代为什么好写。前序顺序是“中左右”根节点最先被处理所以我们可以先把根入栈然后循环弹出节点、输出、把右孩子入栈、把左孩子入栈。因为栈是后进先出先入右孩子就会后处理右孩子弹出顺序恰好是“左 - 右”整体输出就是“中 - 左 - 右”。但后序遍历的问题是根节点最后才处理。你第一次在栈里碰到根节点的时候绝对不能输出得等根节点的左子树和右子树都被处理完。换句话说迭代时需要一种机制让你能区分“第一次碰到这个节点”和“左右子树都处理完了可以输出这个节点了”。这个核心矛盾就是后序迭代比前序迭代麻烦的根源。2.2 方法一双栈法巧妙利用反转双栈法的思路非常讨巧。前序遍历结果是“中左右”后序遍历结果是“左右中”。如果我们能先得到一个“中右左”的结果再把这个结果整体反转不就变成“左右中”了吗问题是怎么得到“中右左”的顺序做法和“中左右”的迭代几乎一样只要把入栈顺序从左先压改成右先压。class Solution { public ListInteger postorderTraversal(TreeNode root) { ListInteger result new ArrayList(); if (root null) { return result; } DequeTreeNode stack new ArrayDeque(); DequeTreeNode outputStack new ArrayDeque(); stack.push(root); while (!stack.isEmpty()) { TreeNode cur stack.pop(); outputStack.push(cur); if (cur.left ! null) { stack.push(cur.left); } if (cur.right ! null) { stack.push(cur.right); } } while (!outputStack.isEmpty()) { result.add(outputStack.pop().val); } return result; } }注意这里入栈的顺序先把左孩子压栈再压右孩子。这样右孩子会先弹出来弹出的顺序就是“根 - 右 - 左”也就是“中右左”。这些弹出的节点被依次压入第二个栈outputStack最后从outputStack里依次弹出就完成了反转得到“左右中”。我第一次写的时候就把左右入栈顺序搞反了。如果先压右孩子再压左孩子弹出的顺序是“中左右”反转之后变成“右左中”完全不是后序遍历。所以这个细节一定要记牢。2.3 方法二单栈标记法用空节点当“信号灯”双栈法思路简单但如果想只用一个栈解决问题可以用标记法。核心思想是在栈里放入一个特殊标记比如null当弹出这个标记时说明栈里的下一个节点是“左右子树都已经处理完”可以直接输出。class Solution { public ListInteger postorderTraversal(TreeNode root) { ListInteger result new ArrayList(); DequeTreeNode stack new ArrayDeque(); if (root ! null) { stack.push(root); } while (!stack.isEmpty()) { TreeNode cur stack.pop(); if (cur ! null) { // 逆序压栈为了输出“左 - 右 - 中”需要按“中 - 右 - 左”的方向准备 stack.push(cur); stack.push(null); if (cur.right ! null) { stack.push(cur.right); } if (cur.left ! null) { stack.push(cur.left); } } else { // 遇到标记弹出下一个节点并输出 result.add(stack.pop().val); } } return result; } }这个代码初看有点绕但只要看懂压栈顺序就通了。我们希望最终弹出顺序是“左、右、中”而栈是后进先出所以压栈时就得倒着来先压当前节点再压一个null标记然后压右孩子最后压左孩子。这样下一次弹出的是左孩子左子树会被优先处理等左子树、右子树都处理完轮到null标记时就说明当前节点在null下面可以输出了。我把这个null理解成一个“信号灯”正常节点弹出后如果不为null就把当前节点压回去并挂一个null在它上方表示“我还没到输出的时候”当弹出null时紧接着弹出并输出它下方的那个节点表示“你的子树都处理完了该你了”。这个方法之后还会在第3章扩展成统一模板前后中序三序遍历一套代码改三行就能切换。2.4 方法三单栈加prev指针模拟递归的本质第三种方法也是最贴近递归本质的方法用一个prev指针记录“上一个被处理的节点”当栈顶节点的右孩子为空或者右孩子恰好是prev时说明当前节点的左右子树都已经处理完可以输出当前节点。class Solution { public ListInteger postorderTraversal(TreeNode root) { ListInteger result new ArrayList(); DequeTreeNode stack new ArrayDeque(); TreeNode cur root; TreeNode prev null; while (cur ! null || !stack.isEmpty()) { while (cur ! null) { stack.push(cur); cur cur.left; } cur stack.peek(); if (cur.right null || cur.right prev) { result.add(cur.val); stack.pop(); prev cur; cur null; } else { cur cur.right; } } return result; } }这段代码里的细节非常多最容易被忽略的是最后一行cur null。为什么要置空因为如果不置空下一次外层while循环又会进入内层while (cur ! null)把当前节点连同左子树再压一遍栈死循环就这么产生了。那什么时候能输出当前节点呢分两种情况第一种是当前节点没有右孩子说明右侧没东西要处理可以直接输出第二种是右孩子刚刚被处理过即cur.right prev说明右子树已经遍历完了。这两个条件只要满足其一就能安全地输出当前节点。这是我实际调试中花了最多时间的逻辑也是后序遍历迭代实现里最容易写错的地方。3. 实操对照代码、验证与统一模板3.1 三种迭代方法对比怎么选面试和实际刷题时不需要每种都背下来但要清楚各自的优劣势。方法思路难度代码量可扩展性适用场景双栈法低少只能处理后序思路直观适合快速写出单栈标记法中中前后中序通用推荐面试使用模板统一prev指针法高多思想上贴近递归理解递归本质后再掌握就我个人的经验如果你现在正处于刷题前期先掌握双栈法和标记法就够了。双栈法帮你建立“先序遍历变体”的直觉标记法帮你理解“如何区分第一次和第二次访问节点”。prev指针法可以作为进阶练习等你对树的遍历有了整体把握之后再去啃它会顺畅得多。3.2 统一模板一套代码应对前中后序用标记法的思路可以再抽象出一个更漂亮的统一模板。核心规律只有一句话输出顺序是“前中后”中的哪一种就把对应顺序反过来压栈并用null分隔。后序输出顺序是“左 - 右 - 中”反过来就是“中 - 右 - 左”。所以代码里的压栈顺序是先压当前节点、再压null、然后压右孩子、最后压左孩子。前序输出顺序是“中 - 左 - 右”反过来是“右 - 左 - 中”。压栈顺序就是先压右孩子、再压左孩子、然后压当前节点、最后压null。中序输出顺序是“左 - 中 - 右”反过来是“右 - 中 - 左”。压栈顺序是先压右孩子、再压当前节点、再压null、最后压左孩子。以中序为例代码长这样class Solution { public ListInteger inorderTraversal(TreeNode root) { ListInteger result new ArrayList(); DequeTreeNode stack new ArrayDeque(); if (root ! null) { stack.push(root); } while (!stack.isEmpty()) { TreeNode cur stack.pop(); if (cur ! null) { if (cur.right ! null) { stack.push(cur.right); } stack.push(cur); stack.push(null); if (cur.left ! null) { stack.push(cur.left); } } else { result.add(stack.pop().val); } } return result; } }掌握了这个模板之后前中后序遍历就不再是三个独立的记忆点而是一个规律。很多人总觉得迭代遍历难其实难在对“栈的先进后出”不够敏感。栈先进后出就像一叠盘子你需要让上面的盘子先被拿走那就得把后处理的内容放在栈顶附近先处理的内容放在栈底位置。入栈顺序和出栈顺序互为镜像把这一点想通模板就自然记住了。3.3 用实际树验证代码正确性写代码容易但写对了没有我建议在本地IDE里把第1章的测试树跑一遍逐步打印中间状态。以双栈法为例模拟几步初始stack [1]outputStack []弹出1outputStack [1]压入左孩子2再压入右孩子3弹出3outputStack [1, 3]压入右孩子6左孩子为空不压弹出6outputStack [1, 3, 6]弹出2outputStack [1, 3, 6, 2]压入左孩子4再压入右孩子5弹出5outputStack [1, 3, 6, 2, 5]弹出4outputStack [1, 3, 6, 2, 5, 4]最后从outputStack逐个弹出4, 5, 2, 6, 3, 1结果和手算完全一致。这个方法的好处是每个中间状态都可追踪调试时非常直观。建议你也画一张类似的表把栈的变化写出来比干看代码有效十倍。3.4 关于“递归转非递归”的拓展认知热词里有一个“快速排序非递归”其实和这题是同一个思维模型。快速排序的递归版本很好写但某些场景下需要转成非递归思路就是用一个栈显式维护“待处理的区间”这和后序遍历的prev指针法本质上完全一致都是在模拟递归的调用栈把隐式的系统栈变成显式的数据结构栈。所以做这道题时不要把目光局限在“会写后序遍历”这一件事上。你在练习的是“如何用栈模拟递归”这种更底层的能力。后面遇到二叉树深度、前中后缀表达式转换、甚至编译原理里的语法树遍历都是同一套思想在复用。这也是为什么很多面试官喜欢在这个题目上深挖迭代实现的原因——他们在考察你对递归思想本质的理解程度。4. 常见报错与排查技巧实录4.1 为什么写二叉树程序总是报运行时错误热词里“写二叉树程序时为什么总是报运行时错误”被很多人搜索说明这是新手最痛的环节。我总结一下最常见的四类第一类空指针异常。root本身是null你还去访问root.left或者某个节点的左孩子是null你直接访问node.left.val。解决办法是在访问节点字段之前先判断节点是否为null递归方法的入口第一行必须写终止条件。第二类递归没有终止条件。递归方法不写if (x null) return函数就会无限调用下去直到栈溢出报StackOverflowError。第三类栈操作越界。迭代时对空栈执行pop()或者pop()之后没有先peek()判断栈是否为空都可能触发EmptyStackException。第四类类型混淆。把TreeNode对象直接添加到结果列表里而不是添加node.val。这类代码编译能通过但结果全是对象的toString()或者类型不匹配直接编译失败。碰到这类问题最快的排查方式是先用空树、单节点树这两个最小用例跑一遍再逐步增加节点数。大多数运行时错误都能在这两步里现出原形。4.2 迭代后序死循环最常见的坑用prev指针法时死循环基本都出在同一个地方当前节点处理完之后没有把cur置为null或者prev更新时机不对。可以加打印语句排查System.out.println(cur (cur null ? null : cur.val) prev (prev null ? null : prev.val) stack.size stack.size());放在外层while循环的末尾。如果发现某个节点的值在日志里反复出现说明cur没有前进也没有成功弹栈。这时需要检查输出当前节点后是否立即stack.pop()、prev是否已更新为当前节点、cur是否被置为null。这三个动作缺一个都会导致下一次循环又回到老节点。4.3 输出顺序不对多半是入栈顺序写反了后序迭代代码跑起来不报错但结果不对最常见的现象是输出结果其实是前序遍历的变体比如4, 2, 5, 1, 6, 3、1, 2, 4, 5, 3, 6这类。如果是双栈法去查第一个栈的入栈顺序必须先压左孩子再压右孩子。如果是标记法去查压栈顺序是否严格满足“反过来压”的规律。后序是“左 - 右 - 中”所以压栈顺序必须是“中 - 右 - 左”用null分隔后实际是“中、null、右、左”。一旦压成“中、null、左、右”输出顺序立刻变成中右左变体。我曾用一棵只有三个节点的树1, 2, 3根1左孩子2右孩子3验证正确的后序结果是2, 3, 1。如果程序输出3, 2, 1说明入栈顺序反了如果输出1, 3, 2说明你还掺杂了前序逻辑。这类最小用例是检验遍历代码最好的试金石。4.4 测试用例速查表刷题时我习惯准备一组覆盖各种形态的测试用例每次写完遍历代码都跑一遍用例树结构预期后序结果空树null[]单节点1[1]只有左子树1 - 2 - 3[3, 2, 1]只有右子树1 - 2 - 3[3, 2, 1]完全二叉树见文中的树[4, 5, 2, 6, 3, 1]如果这些用例全部通过基本可以认定实现是正确的。尤其不要忽略空树和单节点它们最能暴露空指针问题。4.5 本地通过但LeetCode提交报错还有一种常见情况本地IDE里跑得好好的一提交到LeetCode就报错。原因通常有几个你使用了TreeNode类但本地和在线环境的包名/导入不同导致编译错误。你修改了传入的root节点结构导致测试框架后续判断受影响。变量作用域不清比如把结果列表定义在方法外面多次调用时数据没有清空。返回值类型和题目要求不一致比如要求返回ListInteger你却返回了ArrayList这种情况一般能通过但接口不符会报编译错误。解决方案是把方法写成无副作用的纯函数不要在遍历过程中修改原树结果列表在方法内部新建提交前确认类名、方法签名和题目完全一致。踩过几次坑之后我现在提交前都会做这三项检查基本能避开绝大多数提交报错。4.6 关于二叉树遍历的常见问题补充有几个和“二叉树遍历”相关的问题经常一起出现这里顺带提一下。二叉树的深度计算本质上就是在后序遍历的基础上做改造先算左子树深度再算右子树深度最后取最大值加一。为什么用后序因为你要先知道左右子树有多深才能知道当前节点作为根的子树的深度。这和后序遍历“先处理子节点再处理当前节点”完全吻合。搜索二叉树BST的中序遍历结果是升序序列这是BST最重要的性质之一。很多和BST相关的题目比如找第K小的节点都是先做中序遍历再配合计数所以前中后序遍历的迭代写法学扎实了后面做BST题目会轻松很多。线索二叉树则是通过利用空指针域把遍历的前驱和后继信息存起来从而在O(1)空间下完成遍历。它和Morris遍历思想同源属于进阶内容。如果你对“如何在常数额外空间下遍历二叉树”感兴趣可以在掌握本题之后去研究Morris后序遍历那又是一个新的层次。就我个人而言后序遍历的迭代实现是所有二叉树遍历里最值得反复咀嚼的一道题。它表面是考“你会不会写迭代”实际上考的是“你是否真的理解调用栈、理解节点何时可以安全输出、理解显式栈和隐式栈之间的关系”。把这一题吃透前中后序三种遍历、递归转迭代、甚至树的深搜类题目你都会有更踏实的底气。最后再分享一个记忆小技巧后序遍历输出顺序是“左、右、根”迭代时你就记住“根憋到最后才能输出”。不管用哪种方法只要脑子里始终挂着这个判断标准——当前节点是不是已经左右孩子都处理完了——就不会写出离谱的错误答案。刷题这件事没有捷径但把这些关键关口卡住至少能让你少走一大半弯路。
阅读完成 · 觉得有帮助？
