做了十年算法题还有人只会背递归的三行代码一到后序遍历就让面试官看现场翻车这事的根源其实不在“会不会写递归”而在于没搞清楚迭代到底在模拟什么东西。今天我就用 LeetCode 145 这道题把二叉树后序遍历的递归、迭代全拆一遍顺便把“报运行时错误”这个老问题一起解决了。题目本身很简单给定一棵二叉树的根节点返回它的后序遍历结果。所谓后序就是先遍历左子树再遍历右子树最后访问根节点。递归版只要三行迭代版有四五个流派但很多人在面试现场只会写其中一个被追问“为什么这么写”“如果不用栈还能怎么做”就卡住了。这篇就当是 Day38 的学习笔记把每一个方案的原理、代码、坑都讲透适合正在刷二叉树序列、准备算法面试或者刚学到树的同学参考。1. 先把后序遍历的定义和递归轮廓吃透1.1 后序遍历不是“左右根”三个字那么简单教科书上告诉我们遍历顺序是“左子树、右子树、根节点”口诀叫“左右根”前序是“根左右”中序是“左根右”。很多人的误区是只记口诀一上手写递归就蒙。其实你只要把“处理一棵树”这个动作看成三个步骤的排列组合递归函数的写法就顺下来了处理左子树处理右子树访问当前节点。后序这三个步骤的顺序是左、右、当前节点。所以递归代码的骨架极其简单def postorder(root, res): if root is None: return postorder(root.left, res) postorder(root.right, res) res.append(root.val)LeetCode 145 要求返回一个列表所以在主函数里加一层封装def postorderTraversal(root): res [] postorder(root, res) return res这段代码的核心是“先往深处走把所有该处理的子问题处理完最后才碰当前节点”。理解这一点你就能明白为什么后序特别适合“统计子树信息”这类场景比如求二叉树深度、判断平衡二叉树、求解二叉树直径都是先拿左右子树的结果再决定当前节点的状态。实际上“二叉树深度”这类热词题底层几乎都是后序遍历。1.2 为什么后序是三兄弟里最容易写错的前序和中序的迭代写起来都直白后序之所以容易错是因为“根节点最后访问”这个要求破坏了普通栈模拟的直觉。你用栈模拟递归时前序是“入栈后立刻访问”中序是“左路走到底再回来访问”后序呢你遇到根节点时不能马上访问得先等左右子树都处理完这意味着同一个节点可能会被“遇到两次”——一次是打算处理它另一次是真的轮到他访问。如果用简单栈你根本不知道当前是从左子树回来的还是从右子树回来的。这也是为什么后序迭代的解法特别多前序变体反转法、双栈法、颜色标记法、Morris 遍历每一派都是在解决同一个问题——怎么记录“左右子树都处理完了”这个状态。理解了这一层你才算真正吃透这道题而不是单纯记模板。2. 递归实现三行代码的背后是系统栈在替你做状态维护2.1 递归树的展开过程画一遍就能根治“背不下来”我刷题初期最大的弯路是直接背代码结果一换语言、一换题就废。递归的正确打开方式是把一棵简单树手动展开一遍。比如下面这棵树1 / \ 2 3 / \ 4 5后序遍历展开顺序是 4, 5, 2, 3, 1 。看着这个顺序再去看递归执行过程postorder(1) 先调用 postorder(2)postorder(2) 又先调用 postorder(4)4 是一棵空树左右的叶子于是先访问 4再回到 2 去调用 postorder(5)访问 5然后回到 2 访问 2最后回到 1 访问 1……整个过程就是一个“深入左子树、回到父节点、深入右子树、最后访问父节点”的循环。画递归树这一步建议亲手做一遍比刷十遍题都管用。2.2 运行时错误第一坑递归深度过大触发栈溢出标题对应一个非常接地气的热词“写二叉树程序时为什么总是报运行时错误”。二叉树题里最常见的运行时错误并不是算法逻辑错而是递归在极端情况下爆栈。比如一棵链状树每个节点只有左孩子深度是 n递归调用要压 n 层栈帧。Python 默认递归深度大约 1000n 稍微大一点直接报 RecursionError: maximum recursion depth exceeded。LeetCode 官方数据一般不会让 Python 递归直接爆栈但本机测试、面试白板手写、项目里遇到深树时这个问题就非常现实。所以我一般给三条建议刷题阶段先实现递归版保证思路正确面试时主动提一句“递归版会爆栈我可以给出迭代版”这往往是加分项不要试图通过 sys.setrecursionlimit(1000000) 无限拉高深度因为 C 调用栈有物理上限拉过头会直接段错误崩溃。2.3 递归转迭代的真正动机不是炫技是可控很多人觉得迭代是面试官的刁难其实不是。递归方便但它把控制权交给系统栈迭代把栈变成显式数据结构内存可控、过程可观测、也能避免爆栈。项目里处理超深树、或者写通用遍历框架时迭代版更稳。另外如果你在学迭代器热词里也有“迭代器”“python 生成数据批量加载的迭代器”这类内容你会发现后序遍历的迭代版天然适合写成一个生成器每调一次 next 就吐出一个节点值这对内存优化非常有价值。后面我给的标记法模板稍微改造就能变生成器。3. 迭代实现三个主流方案一次讲透3.1 方案一前序变体 反转最骗人也最实用先看一个投机取巧但非常常用的思路。前序遍历是“根左右”后序遍历是“左右根”。我们把前序改成“根右左”再反转一下就变成了“左右根”。具体做法用栈做“根右左”的遍历先访问根然后压入左子树、再压入右子树这样弹出顺序是根、右、左最后把整个结果列表反转得到左、右、根。直接上代码def postorderTraversal(root): if not root: return [] stack [root] res [] while stack: node stack.pop() res.append(node.val) if node.left: stack.append(node.left) if node.right: stack.append(node.right) return res[::-1]这个方案我愿称之为“背模板最快版本”。前序迭代大部分人都会入栈根、出栈访问、先压右再压左。把这里改成“先压左再压右”得到“根右左”最后反过来就是后序。代码短、不容易错、面试讲起来也通畅。但有一个大坑不要把“根右左”和“反转”的顺序弄反也不要忘了反转。我在牛客评论区看过不少次有人输出成了根右左或者把反转写成了 reverseTrue 的排序纯纯粗心。3.2 方案二双栈法理解能力强但实战效率一般双栈法是更“正统”的模拟思路第一个栈负责遍历顺序第二个栈负责最终结果的逆序存储。流程是这样的根节点入栈栈1 弹出节点节点放入栈2先把该节点的左孩子压入栈1再把右孩子压入栈1注意顺序栈1 为空时把栈2 依次弹出即为后序遍历结果。代码def postorderTraversal(root): if not root: return [] s1, s2 [root], [] while s1: node s1.pop() s2.append(node) if node.left: s1.append(node.left) if node.right: s1.append(node.right) res [] while s2: res.append(s2.pop().val) return res为什么 s2 直接弹出就是答案因为 s1 的弹出顺序是“根左右”先压右后压左会变成根左右这里我们压的是左再右s2 按这个顺序接收最后反过来弹出就变成“左右根”。双栈法的时间复杂度 O(n)、空间 O(n)理解上很顺但临时多了一个栈代码也比方案一长所以实际刷题我很少推荐它了解即可。3.3 方案三单栈 上次访问标记最贴近递归本质这个方案是我个人最喜欢也最推荐掌握的因为它能彻底回答“怎么知道左右子树处理完了”这个问题。用一个栈保存待处理节点用一个 prev 变量记录上一次访问的节点。循环逻辑把当前节点一路向左压栈当左路走到底时取出栈顶但不急着弹出——看它的右子树如果右子树为空或右子树刚刚被访问完也就是 prev 等于右孩子说明左右都处理完了可以访问当前节点并弹出否则说明右子树还没处理继续去处理右子树。def postorderTraversal(root): res [] stack [] cur root prev None while cur or stack: while cur: stack.append(cur) cur cur.left node stack[-1] if node.right is None or node.right prev: res.append(node.val) stack.pop() prev node else: cur node.right return res这个代码第一次看会有点绕但它是所有迭代方案里“最像递归”的左路压栈相当于递归调用左子树prev 记录相当于递归返回后系统栈帮你保存的“上一次执行到哪一步”状态。你把这个过程在纸上走一遍树是 [1,2,3]先压 1再压 22 没有左右孩子于是访问 2 并弹出prev2此时栈顶是 1它右孩子是 3不等于 prev所以 cur3继续处理……最后 1 的右子树 3 处理完prev3再回头访问 1。这个方案的另一个好处是空间复杂度在最坏情况下链状树是 O(n)但一般树情况下它比双栈法省了一个栈也更容易改造成生成器def postorder_iter(root): stack, cur, prev [], root, None while cur or stack: while cur: stack.append(cur) cur cur.left node stack[-1] if node.right is None or node.right prev: yield node.val prev node stack.pop() else: cur node.right想用迭代器处理超大树的数据流这个小改造就是现成的实现。3.4 方案四颜色标记法一套模板吃遍三种遍历颜色标记法至少在我看的博客圈里已经是“统一模板”的代名词了。它的思路是用一个二元组 (node, visited) 入栈visitedFalse 表示还没访问过visitedTrue 表示该访问了。遍历时如果 node 不为空且未访问过按照后序“左、右、根”的逆序入栈先压 (根, True)再压 (右, False)最后压 (左, False)。因为栈是后进先出压栈顺序要反过来如果标记为 True直接输出值。def postorderTraversal(root): res [] stack [(root, False)] while stack: node, visited stack.pop() if node is None: continue if visited: res.append(node.val) else: stack.append((node, True)) stack.append((node.right, False)) stack.append((node.left, False)) return res把这三行的入栈顺序调整一下就能得到前序和中序的迭代版。所以如果你不想记三套迭代模板记这一套就够了。代价是每个节点要额外标记一次空间略增但绝对值 O(n)可接受。4. 复杂度对比与前中后序迭代规律总结4.1 时间和空间两个维度怎么取舍先看一张总结表把上面几个方案摊开方案时间复杂度空间复杂度代码量推荐场景递归O(n)O(h)h 为树高最短思路验证、子树信息统计前序变体反转O(n)O(n)短面试快速作答双栈O(n)O(n)中理解遍历方向翻转单栈prevO(n)O(n)中最贴近递归的迭代版颜色标记法O(n)O(n)短一套模板通吃三种遍历MorrisO(n)O(1)最长追求常量空间、进阶考察注意这里 h 是树高最坏情况 hn链状树所以递归空间最坏也是 O(n)。很多人误以为递归空间是 O(logn)那是平衡树的理想情况面试时严谨一点要说 O(h)。4.2 前中后序迭代的统一套路压栈顺序和访问时机三个遍历用颜色标记法核心逻辑其实只有一条你想让节点以什么顺序被弹出就按相反顺序压栈。前序要“根左右”压栈就压“右、左、根”的逆序并把访问时机放到节点弹出时中序要“左根右”就压“右、根、左”后序要“左右根”就压“根、右、左”。这种“逆序压栈、正序出栈”的思想不只在二叉树里有在快速排序的非递归实现里同样成立——把一次快排分割看成对左右区间的“处理”用栈保存待排序区间本质上就是用一个显式栈模拟递归调用。热词里出现“快速排序非递归”很多人转不过弯其实你只要把“函数递归”替换成“手动维护任务栈”就豁然开朗了。5. 运行时错误排查实录五个我踩过且你在评论区大概率见过的坑5.1 空树和 None 判断没写不管递归还是迭代第一步都必须处理root is None。迭代版里如果你没判空直接stack[root]没问题但访问node.val前没检查 node 是否 None空树就崩了。颜色标记法里如果不跳过 None也会尝试访问 None 的属性。我最常看到的新手代码是这种def postorderTraversal(root): res [] if not root: # 这行其实可以不要 return res stack [root] while stack: cur stack.pop() res.append(cur.val) # 如果 cur 可能是 None这里早晚崩 ...正确做法是要么在入栈前就排除 None要么在弹出后判 None。没有银弹选一种坚持到底。5.2 输出顺序恰好是“前序”或“根右左”后序遍历的迭代最容易出现这种让人崩溃的“看起来很像但顺序不对”。根因就是方案一没反转或者颜色标记法压栈顺序写反。排查方法只有一个拿一棵三层满二叉树比如1 - left:2, right:32 - left:4, right:5手动走一遍输出应该和递归版完全一致。凡是和递归版对不上的八成是顺序问题不是类型问题。5.3 二叉树的深度牵扯出的空指针隐患热词里还有“二叉树的深度”后序正好能求深度。很多人在做深度题时代码没问题但到了后序遍历想着“顺手求个深度”把 depth 的更新时机弄错导致最后读 None。这里讲一个通用经验后序处理节点时子树信息已经完备可以先 depth_left、depth_right 都用递归拿到再算当前节点深度。这个模式一旦熟练二叉树直径、平衡判断、最大路径和都是一样套路学一题会一串。5.4 栈溢出不仅仅是递归的专利虽然迭代不爆递归栈但方案二双栈法和方案三单栈法如果在大数据量下没控制好额外的栈结构会占 O(n) 内存极端情况下可能内存紧张。真正要做到常量空间得上 Morris 遍历——它在遍历过程中临时改造树结构把右孩子指针指回前驱后序 Morris 是所有遍历里最复杂的面试很少让写我建议先掌握思路别作为优先方向。5.5 调试建议打印遍历过程别只盯错误“为什么报运行时错误”的最好答案其实是“学会单步调试”。Python 刷题可以这样做from collections import deque def debug_postorder(root): res [] stack [(root, False)] while stack: node, visited stack.pop() if node is None: continue print(fpop node{node.val}, visited{visited}) if visited: res.append(node.val) else: stack.append((node, True)) stack.append((node.right, False)) stack.append((node.left, False)) return res如果输出结果不对只要看打印的顺序就能定位是压栈顺序反了还是 visited 标记没生效。这个调试手段对迭代遍历特别好用强烈建议在本地照抄一份。6. 一些个人的实操体会6.1 我的模板使用策略刷题这些年我最后的后序方案固定成了“迭代优先选标记法笔试选前序变体”。原因很现实笔试时间紧前序变体三分钟写完正确率也高面试被追问原理时再切换成标记法详细解释展示你是真懂而不是背模板。递归版一定要会写因为很多子问题题是递归思路为主迭代反而不直观。6.2 最后分享一个写树题防坑的小技巧写任何二叉树题之前先在注释里写三行伪代码# 1. 空树返回什么 # 2. 单节点返回什么 # 3. 左右子树怎么合并这三行想清楚运行时错误能少一半。后序遍历的返回值是一个列表空树应该是空列表而不是 None单节点应该返回 [root.val]左右子树的结果要按“左-右-根”拼接。养成这个习惯之后你写二叉树题的速度和准确率都会有肉眼可见的提升这套方法也不只适用于后序中序、前序、层序都一样管用。 
长河君 · 2026/10/10 18:35:05 · 阅读 1.2k 二叉树后序遍历全解：递归、迭代与运行时错误排查
做了十年算法题还有人只会背递归的三行代码一到后序遍历就让面试官看现场翻车这事的根源其实不在“会不会写递归”而在于没搞清楚迭代到底在模拟什么东西。今天我就用 LeetCode 145 这道题把二叉树后序遍历的递归、迭代全拆一遍顺便把“报运行时错误”这个老问题一起解决了。题目本身很简单给定一棵二叉树的根节点返回它的后序遍历结果。所谓后序就是先遍历左子树再遍历右子树最后访问根节点。递归版只要三行迭代版有四五个流派但很多人在面试现场只会写其中一个被追问“为什么这么写”“如果不用栈还能怎么做”就卡住了。这篇就当是 Day38 的学习笔记把每一个方案的原理、代码、坑都讲透适合正在刷二叉树序列、准备算法面试或者刚学到树的同学参考。1. 先把后序遍历的定义和递归轮廓吃透1.1 后序遍历不是“左右根”三个字那么简单教科书上告诉我们遍历顺序是“左子树、右子树、根节点”口诀叫“左右根”前序是“根左右”中序是“左根右”。很多人的误区是只记口诀一上手写递归就蒙。其实你只要把“处理一棵树”这个动作看成三个步骤的排列组合递归函数的写法就顺下来了处理左子树处理右子树访问当前节点。后序这三个步骤的顺序是左、右、当前节点。所以递归代码的骨架极其简单def postorder(root, res): if root is None: return postorder(root.left, res) postorder(root.right, res) res.append(root.val)LeetCode 145 要求返回一个列表所以在主函数里加一层封装def postorderTraversal(root): res [] postorder(root, res) return res这段代码的核心是“先往深处走把所有该处理的子问题处理完最后才碰当前节点”。理解这一点你就能明白为什么后序特别适合“统计子树信息”这类场景比如求二叉树深度、判断平衡二叉树、求解二叉树直径都是先拿左右子树的结果再决定当前节点的状态。实际上“二叉树深度”这类热词题底层几乎都是后序遍历。1.2 为什么后序是三兄弟里最容易写错的前序和中序的迭代写起来都直白后序之所以容易错是因为“根节点最后访问”这个要求破坏了普通栈模拟的直觉。你用栈模拟递归时前序是“入栈后立刻访问”中序是“左路走到底再回来访问”后序呢你遇到根节点时不能马上访问得先等左右子树都处理完这意味着同一个节点可能会被“遇到两次”——一次是打算处理它另一次是真的轮到他访问。如果用简单栈你根本不知道当前是从左子树回来的还是从右子树回来的。这也是为什么后序迭代的解法特别多前序变体反转法、双栈法、颜色标记法、Morris 遍历每一派都是在解决同一个问题——怎么记录“左右子树都处理完了”这个状态。理解了这一层你才算真正吃透这道题而不是单纯记模板。2. 递归实现三行代码的背后是系统栈在替你做状态维护2.1 递归树的展开过程画一遍就能根治“背不下来”我刷题初期最大的弯路是直接背代码结果一换语言、一换题就废。递归的正确打开方式是把一棵简单树手动展开一遍。比如下面这棵树1 / \ 2 3 / \ 4 5后序遍历展开顺序是 4, 5, 2, 3, 1 。看着这个顺序再去看递归执行过程postorder(1) 先调用 postorder(2)postorder(2) 又先调用 postorder(4)4 是一棵空树左右的叶子于是先访问 4再回到 2 去调用 postorder(5)访问 5然后回到 2 访问 2最后回到 1 访问 1……整个过程就是一个“深入左子树、回到父节点、深入右子树、最后访问父节点”的循环。画递归树这一步建议亲手做一遍比刷十遍题都管用。2.2 运行时错误第一坑递归深度过大触发栈溢出标题对应一个非常接地气的热词“写二叉树程序时为什么总是报运行时错误”。二叉树题里最常见的运行时错误并不是算法逻辑错而是递归在极端情况下爆栈。比如一棵链状树每个节点只有左孩子深度是 n递归调用要压 n 层栈帧。Python 默认递归深度大约 1000n 稍微大一点直接报 RecursionError: maximum recursion depth exceeded。LeetCode 官方数据一般不会让 Python 递归直接爆栈但本机测试、面试白板手写、项目里遇到深树时这个问题就非常现实。所以我一般给三条建议刷题阶段先实现递归版保证思路正确面试时主动提一句“递归版会爆栈我可以给出迭代版”这往往是加分项不要试图通过 sys.setrecursionlimit(1000000) 无限拉高深度因为 C 调用栈有物理上限拉过头会直接段错误崩溃。2.3 递归转迭代的真正动机不是炫技是可控很多人觉得迭代是面试官的刁难其实不是。递归方便但它把控制权交给系统栈迭代把栈变成显式数据结构内存可控、过程可观测、也能避免爆栈。项目里处理超深树、或者写通用遍历框架时迭代版更稳。另外如果你在学迭代器热词里也有“迭代器”“python 生成数据批量加载的迭代器”这类内容你会发现后序遍历的迭代版天然适合写成一个生成器每调一次 next 就吐出一个节点值这对内存优化非常有价值。后面我给的标记法模板稍微改造就能变生成器。3. 迭代实现三个主流方案一次讲透3.1 方案一前序变体 反转最骗人也最实用先看一个投机取巧但非常常用的思路。前序遍历是“根左右”后序遍历是“左右根”。我们把前序改成“根右左”再反转一下就变成了“左右根”。具体做法用栈做“根右左”的遍历先访问根然后压入左子树、再压入右子树这样弹出顺序是根、右、左最后把整个结果列表反转得到左、右、根。直接上代码def postorderTraversal(root): if not root: return [] stack [root] res [] while stack: node stack.pop() res.append(node.val) if node.left: stack.append(node.left) if node.right: stack.append(node.right) return res[::-1]这个方案我愿称之为“背模板最快版本”。前序迭代大部分人都会入栈根、出栈访问、先压右再压左。把这里改成“先压左再压右”得到“根右左”最后反过来就是后序。代码短、不容易错、面试讲起来也通畅。但有一个大坑不要把“根右左”和“反转”的顺序弄反也不要忘了反转。我在牛客评论区看过不少次有人输出成了根右左或者把反转写成了 reverseTrue 的排序纯纯粗心。3.2 方案二双栈法理解能力强但实战效率一般双栈法是更“正统”的模拟思路第一个栈负责遍历顺序第二个栈负责最终结果的逆序存储。流程是这样的根节点入栈栈1 弹出节点节点放入栈2先把该节点的左孩子压入栈1再把右孩子压入栈1注意顺序栈1 为空时把栈2 依次弹出即为后序遍历结果。代码def postorderTraversal(root): if not root: return [] s1, s2 [root], [] while s1: node s1.pop() s2.append(node) if node.left: s1.append(node.left) if node.right: s1.append(node.right) res [] while s2: res.append(s2.pop().val) return res为什么 s2 直接弹出就是答案因为 s1 的弹出顺序是“根左右”先压右后压左会变成根左右这里我们压的是左再右s2 按这个顺序接收最后反过来弹出就变成“左右根”。双栈法的时间复杂度 O(n)、空间 O(n)理解上很顺但临时多了一个栈代码也比方案一长所以实际刷题我很少推荐它了解即可。3.3 方案三单栈 上次访问标记最贴近递归本质这个方案是我个人最喜欢也最推荐掌握的因为它能彻底回答“怎么知道左右子树处理完了”这个问题。用一个栈保存待处理节点用一个 prev 变量记录上一次访问的节点。循环逻辑把当前节点一路向左压栈当左路走到底时取出栈顶但不急着弹出——看它的右子树如果右子树为空或右子树刚刚被访问完也就是 prev 等于右孩子说明左右都处理完了可以访问当前节点并弹出否则说明右子树还没处理继续去处理右子树。def postorderTraversal(root): res [] stack [] cur root prev None while cur or stack: while cur: stack.append(cur) cur cur.left node stack[-1] if node.right is None or node.right prev: res.append(node.val) stack.pop() prev node else: cur node.right return res这个代码第一次看会有点绕但它是所有迭代方案里“最像递归”的左路压栈相当于递归调用左子树prev 记录相当于递归返回后系统栈帮你保存的“上一次执行到哪一步”状态。你把这个过程在纸上走一遍树是 [1,2,3]先压 1再压 22 没有左右孩子于是访问 2 并弹出prev2此时栈顶是 1它右孩子是 3不等于 prev所以 cur3继续处理……最后 1 的右子树 3 处理完prev3再回头访问 1。这个方案的另一个好处是空间复杂度在最坏情况下链状树是 O(n)但一般树情况下它比双栈法省了一个栈也更容易改造成生成器def postorder_iter(root): stack, cur, prev [], root, None while cur or stack: while cur: stack.append(cur) cur cur.left node stack[-1] if node.right is None or node.right prev: yield node.val prev node stack.pop() else: cur node.right想用迭代器处理超大树的数据流这个小改造就是现成的实现。3.4 方案四颜色标记法一套模板吃遍三种遍历颜色标记法至少在我看的博客圈里已经是“统一模板”的代名词了。它的思路是用一个二元组 (node, visited) 入栈visitedFalse 表示还没访问过visitedTrue 表示该访问了。遍历时如果 node 不为空且未访问过按照后序“左、右、根”的逆序入栈先压 (根, True)再压 (右, False)最后压 (左, False)。因为栈是后进先出压栈顺序要反过来如果标记为 True直接输出值。def postorderTraversal(root): res [] stack [(root, False)] while stack: node, visited stack.pop() if node is None: continue if visited: res.append(node.val) else: stack.append((node, True)) stack.append((node.right, False)) stack.append((node.left, False)) return res把这三行的入栈顺序调整一下就能得到前序和中序的迭代版。所以如果你不想记三套迭代模板记这一套就够了。代价是每个节点要额外标记一次空间略增但绝对值 O(n)可接受。4. 复杂度对比与前中后序迭代规律总结4.1 时间和空间两个维度怎么取舍先看一张总结表把上面几个方案摊开方案时间复杂度空间复杂度代码量推荐场景递归O(n)O(h)h 为树高最短思路验证、子树信息统计前序变体反转O(n)O(n)短面试快速作答双栈O(n)O(n)中理解遍历方向翻转单栈prevO(n)O(n)中最贴近递归的迭代版颜色标记法O(n)O(n)短一套模板通吃三种遍历MorrisO(n)O(1)最长追求常量空间、进阶考察注意这里 h 是树高最坏情况 hn链状树所以递归空间最坏也是 O(n)。很多人误以为递归空间是 O(logn)那是平衡树的理想情况面试时严谨一点要说 O(h)。4.2 前中后序迭代的统一套路压栈顺序和访问时机三个遍历用颜色标记法核心逻辑其实只有一条你想让节点以什么顺序被弹出就按相反顺序压栈。前序要“根左右”压栈就压“右、左、根”的逆序并把访问时机放到节点弹出时中序要“左根右”就压“右、根、左”后序要“左右根”就压“根、右、左”。这种“逆序压栈、正序出栈”的思想不只在二叉树里有在快速排序的非递归实现里同样成立——把一次快排分割看成对左右区间的“处理”用栈保存待排序区间本质上就是用一个显式栈模拟递归调用。热词里出现“快速排序非递归”很多人转不过弯其实你只要把“函数递归”替换成“手动维护任务栈”就豁然开朗了。5. 运行时错误排查实录五个我踩过且你在评论区大概率见过的坑5.1 空树和 None 判断没写不管递归还是迭代第一步都必须处理root is None。迭代版里如果你没判空直接stack[root]没问题但访问node.val前没检查 node 是否 None空树就崩了。颜色标记法里如果不跳过 None也会尝试访问 None 的属性。我最常看到的新手代码是这种def postorderTraversal(root): res [] if not root: # 这行其实可以不要 return res stack [root] while stack: cur stack.pop() res.append(cur.val) # 如果 cur 可能是 None这里早晚崩 ...正确做法是要么在入栈前就排除 None要么在弹出后判 None。没有银弹选一种坚持到底。5.2 输出顺序恰好是“前序”或“根右左”后序遍历的迭代最容易出现这种让人崩溃的“看起来很像但顺序不对”。根因就是方案一没反转或者颜色标记法压栈顺序写反。排查方法只有一个拿一棵三层满二叉树比如1 - left:2, right:32 - left:4, right:5手动走一遍输出应该和递归版完全一致。凡是和递归版对不上的八成是顺序问题不是类型问题。5.3 二叉树的深度牵扯出的空指针隐患热词里还有“二叉树的深度”后序正好能求深度。很多人在做深度题时代码没问题但到了后序遍历想着“顺手求个深度”把 depth 的更新时机弄错导致最后读 None。这里讲一个通用经验后序处理节点时子树信息已经完备可以先 depth_left、depth_right 都用递归拿到再算当前节点深度。这个模式一旦熟练二叉树直径、平衡判断、最大路径和都是一样套路学一题会一串。5.4 栈溢出不仅仅是递归的专利虽然迭代不爆递归栈但方案二双栈法和方案三单栈法如果在大数据量下没控制好额外的栈结构会占 O(n) 内存极端情况下可能内存紧张。真正要做到常量空间得上 Morris 遍历——它在遍历过程中临时改造树结构把右孩子指针指回前驱后序 Morris 是所有遍历里最复杂的面试很少让写我建议先掌握思路别作为优先方向。5.5 调试建议打印遍历过程别只盯错误“为什么报运行时错误”的最好答案其实是“学会单步调试”。Python 刷题可以这样做from collections import deque def debug_postorder(root): res [] stack [(root, False)] while stack: node, visited stack.pop() if node is None: continue print(fpop node{node.val}, visited{visited}) if visited: res.append(node.val) else: stack.append((node, True)) stack.append((node.right, False)) stack.append((node.left, False)) return res如果输出结果不对只要看打印的顺序就能定位是压栈顺序反了还是 visited 标记没生效。这个调试手段对迭代遍历特别好用强烈建议在本地照抄一份。6. 一些个人的实操体会6.1 我的模板使用策略刷题这些年我最后的后序方案固定成了“迭代优先选标记法笔试选前序变体”。原因很现实笔试时间紧前序变体三分钟写完正确率也高面试被追问原理时再切换成标记法详细解释展示你是真懂而不是背模板。递归版一定要会写因为很多子问题题是递归思路为主迭代反而不直观。6.2 最后分享一个写树题防坑的小技巧写任何二叉树题之前先在注释里写三行伪代码# 1. 空树返回什么 # 2. 单节点返回什么 # 3. 左右子树怎么合并这三行想清楚运行时错误能少一半。后序遍历的返回值是一个列表空树应该是空列表而不是 None单节点应该返回 [root.val]左右子树的结果要按“左-右-根”拼接。养成这个习惯之后你写二叉树题的速度和准确率都会有肉眼可见的提升这套方法也不只适用于后序中序、前序、层序都一样管用。