企业官网建设流程全解析

做了十年算法题还有人只会背递归的三行代码，一到后序遍历就让面试官看现场翻车，这事的根源其实不在“会不会写递归”，而在于没搞清楚迭代到底在模拟什么东西。今天我就用 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 默认递归深度大约 1000，n 稍微大一点，直接报 RecursionError: maximum recursion depth exceeded。

LeetCode 官方数据一般不会让 Python 递归直接爆栈，但本机测试、面试白板手写、项目里遇到深树时，这个问题就非常现实。所以我一般给三条建议：

1. 刷题阶段先实现递归版，保证思路正确；
2. 面试时主动提一句“递归版会爆栈，我可以给出迭代版”，这往往是加分项；
3. 不要试图通过 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]

这个方案我愿称之为“背模板最快版本”。前序迭代大部分人都会：入栈根、出栈访问、先压右再压左。把这里改成“先压左再压右”，得到“根右左”，最后反过来就是后序。代码短、不容易错、面试讲起来也通畅。

但有一个大坑：不要把“根右左”和“反转”的顺序弄反，也不要忘了反转。我在牛客评论区看过不少次有人输出成了根右左，或者把反转写成了 reverse=True 的排序，纯纯粗心。

3.2 方案二：双栈法，理解能力强但实战效率一般

双栈法是更“正统”的模拟思路：第一个栈负责遍历顺序，第二个栈负责最终结果的逆序存储。流程是这样的：

1. 根节点入栈；
2. 栈1 弹出节点，节点放入栈2；
3. 先把该节点的左孩子压入栈1，再把右孩子压入栈1（注意顺序）；
4. 栈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 变量记录上一次访问的节点。循环逻辑：

1. 把当前节点一路向左压栈；
2. 当左路走到底时，取出栈顶但不急着弹出——看它的右子树；
3. 如果右子树为空或右子树刚刚被访问完（也就是 prev 等于右孩子），说明左右都处理完了，可以访问当前节点并弹出；
4. 否则，说明右子树还没处理，继续去处理右子树。

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，再压 2，2 没有左右孩子，于是访问 2 并弹出，prev=2；此时栈顶是 1，它右孩子是 3，不等于 prev，所以 cur=3继续处理……最后 1 的右子树 3 处理完，prev=3，再回头访问 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) 入栈，visited=False 表示还没访问过，visited=True 表示该访问了。遍历时：

• 如果 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 时间和空间两个维度怎么取舍

先看一张总结表，把上面几个方案摊开：

注意这里 h 是树高，最坏情况 h=n（链状树），所以递归空间最坏也是 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:3，2 -> 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(f"pop 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]；左右子树的结果要按“左->右->根”拼接。养成这个习惯之后，你写二叉树题的速度和准确率都会有肉眼可见的提升，这套方法也不只适用于后序，中序、前序、层序都一样管用。