最近帮一位朋友复盘二叉树前中后序遍历的迭代遍历我忽然意识到这个知识点在算法学习里的位置确实被低估了。很多人能闭眼背出递归版本的三行代码但一旦被追问“递归底层靠什么机制跑起来的”“如果二叉树退化成链表递归会不会出事”就开始支支吾吾。迭代遍历不是“面试官故意为难你”的花活它本质上是在回答一个问题当你不依赖系统帮你维护调用栈时你自己能不能用显式的栈把递归的行为完整模拟出来。这篇文章不打算绕弯直接从“为什么递归好用但有隐患”讲起把前序、中序、后序三种迭代写法的核心思路、代码模板、踩坑记录一次说透。它适合正在刷题准备面试的人适合刚学完递归想彻底理解栈与遍历顺序关系的人也适合那种“代码能跑但讲不清楚为什么”的朋友。读完你至少能达成三个目标能默写三种迭代遍历能解释每一行代码背后的意图遇到后续更复杂的树形DP、最近公共祖先等问题时敢用栈去模拟递归而不发怵。1. 为什么迭代遍历是绕不过去的一道坎1.1 递归的优雅与隐藏的隐患先看一眼递归版本到底做了什么。前序遍历的递归写法大概是这样的先处理根节点再递归处理左子树最后递归处理右子树。中序和后序只是交换了三句话的顺序。这种写法极简符合人的思维直觉阅读起来像在念一段自然的流程说明。但你有没有想过递归在机器层面是怎么执行的每次递归调用操作系统都会往“调用栈”里压入一个栈帧栈帧里保存了当前函数的返回地址、参数值、局部变量。递归到叶子节点时栈已经被压了树的深度那么多层一层层返回时再弹出这些栈帧。换句话说递归版的遍历顺序本质上就是由系统调用栈的压栈、弹栈时机决定的。这带来两个隐患。第一二叉树的深度可能很大。最坏情况下一棵树退化成类似链表的结构深度就是节点数量。如果有一万个节点递归调用时系统栈就得压一万层很容易触发栈溢出。这在工作环境中不是危言耸听很多线上服务出现栈溢出的崩溃日志根因就是递归深度失控。第二面试场景下考官经常会追问“能不能不用递归写一遍”。如果只背了递归模板当场就会露怯。这两个问题都指向同一个解自己维护一个栈把递归过程显式化。1.2 用显式栈模拟递归的底层思路把系统调用栈换成自己的栈听起来很抽象其实可以打个比方。递归版本的每一次函数调用相当于往桌上放一张写着“待办事项”的纸条处理完一个子问题就揭掉最上面的纸条继续看下一张。迭代遍历要做的就是自己管理这摞纸条你用代码决定什么时候放纸条、什么时候取纸条、取出来之后做什么。栈的特点大家都熟后进先出。这意味着如果你希望某个节点先被访问你在压栈时就要让它后进栈。比如前序遍历想先访问根再访问左子树最后访问右子树那么你弹出一个节点后需要先把右子树压栈再把左子树压栈。这样左子树节点反而在栈的上面下一轮循环先被弹出处理。压栈顺序和最终访问顺序正好相反这个“反直觉”的点正是迭代遍历最容易出错的地方。顺着这个思路你会发现三种遍历的迭代写法不是三个孤立的模板而是同一件事的不同处理节奏什么时候把根节点当“待办事项”取出来访问决定了最终输出顺序。后面几节就按前序、中序、后序的顺序逐个拆开。2. 前序遍历先看懂最简单的“压栈顺序”2.1 思路根左右栈是倒着放的前序遍历的访问顺序是“根节点、左子树、右子树”在递归写法里你要在进入左子树前先访问根在迭代写法里这个动作变成了“遇到一个节点立刻处理它”。由于栈是后进先出想让左子树先于右子树被访问压栈时就要反着来先压右孩子再压左孩子。这个顺序是前序遍历迭代版的灵魂。先压右孩子右孩子被压在栈底再压左孩子左孩子在栈顶。下一轮循环弹出时左孩子先被处理正好符合“先左后右”。代码结构其实很直接def preorder_iter(root): if not root: return [] res [] stack [root] while stack: node stack.pop() res.append(node.val) if node.right: stack.append(node.right) if node.left: stack.append(node.left) return res这段代码里有一个容易忽略的小细节判断空节点。压栈前先检查右孩子和左孩子是否为空可以避免把空指针压入栈里省掉后续循环里的空判断。对于空树开头直接返回空列表也避免了对空指针取属性报错。2.2 手跑一遍五节点样例光看代码可能不够直观拿一棵具体的树走一遍。树的结构是这样根节点是11的左孩子是2右孩子是32的左孩子是4右孩子是5。正确的前序遍历结果是1, 2, 4, 5, 3。迭代过程分成几步走初始时栈为 [1]。 第一步弹出1输出1压入右孩子3再压入左孩子2。此时栈从底到顶是 [3, 2]栈顶是2。 第二步弹出2输出2压入2的右孩子5再压入2的左孩子4。栈从底到顶是 [3, 5, 4]栈顶是4。 第三步弹出4输出44没有孩子不做压栈操作。栈剩 [3, 5]栈顶是5。 第四步弹出5输出55没有孩子。栈剩 [3]。 第五步弹出3输出3。输出序列是1, 2, 4, 5, 3和递归前序完全一致。整个过程里节点被压进栈的次数正好等于它被访问的次数每个节点都只入栈出栈一次时间复杂度是O(n)空间复杂度最坏情况下是O(n)。注意如果你不小心把压栈顺序写成先压左孩子再压右孩子上面的输出会变成1, 3, 2, 5, 4这就变成了“根右左”不是前序遍历了。这种错误特别隐蔽因为代码照样能跑出结果只有和标准答案对比时才会发现问题。2.3 为什么这个写法最“省心”前序迭代版本之所以被放在最前面讲是因为它和“每当处理一个节点立刻输出”的直觉最贴近。你不需要像中序那样考虑“什么时候才能访问根”也不需要像后序那样判断“根是不是已经从右子树回来了”。只要记住“弹栈即访问先压右再压左”基本不会出错。实际用的时候我还习惯把空判断放到循环开头统一处理代码行数更少。但那种写法会把空节点压入栈增加无意义的循环次数。个人建议面试时用先判断再压栈的版本少一些边界情况讲起来思路也更顺。3. 中序遍历一路走到最左边再开始访问3.1 思路先奔着左边界去弹出来再向右中序遍历的访问顺序是“左子树、根节点、右子树”。和递归版本相对应迭代时你想模拟的是先一路递归进左子树直到左孩子为空然后访问这个“最左的节点”再处理它的右子树。这个“一路向左”的过程表现在代码里就是用一个内层循环不断压栈def inorder_iter(root): res [] stack [] cur root while cur or stack: while cur: stack.append(cur) cur cur.left node stack.pop() res.append(node.val) cur node.right return res外层循环的判断条件是cur or stack这个条件值得多说两句。cur不为空说明还有节点需要往左探索并压栈stack不为空说明还有已经压过栈但尚未访问的节点。二者缺一不可。只写while cur一旦走到最左的空节点循环直接退出后面的根节点和右子树都不会被处理只写while stack初始时栈为空空树的时候直接不进入循环看起来没问题但遇到右子树存在的情况你没有办法从当前节点继续往右走。整个算法的节奏可以概括成四步能往左就往左压栈压到不能压为止弹出一个节点并访问转到该节点的右孩子继续重复。3.2 中序迭代为什么要区分“压栈”和“访问”中序和前序最大的不同在于访问节点的时机。前序里节点一从栈里弹出来就访问因为根最先处理中序里节点从栈里弹出来也不能随便访问必须先把它所有的左子树压完。你可以把中序的压栈过程理解为“攒着不处理”。每压入一个节点都是因为它在等待它的左子树先被访问。直到当前节点没有左孩子才弹出这个节点这时候它的左子树一定已经全部处理完了弹出的时机正好对应递归中“左子树递归返回后访问根节点”的瞬间。为了把这个时机说清楚还拿上一节的那棵树走一遍中序。正确的中序输出是4, 2, 5, 1, 3。cur 从根节点1开始。 先把1、2、4依次压栈因为从1出发左孩子是22的左孩子是4。此时栈从底到顶是 [1, 2, 4]。 4没有左孩子弹4输出4。此时 cur 被赋值为4的右孩子为空。 栈顶是2弹2输出2。cur 被赋值为2的右孩子5。 cur 为5非空把5压栈。5没有左孩子弹5输出5。 栈顶是1弹1输出1。cur 被赋值为1的右孩子3。 把3压栈3没有左孩子弹3输出3。输出的顺序恰好是左、根、右一层层展开的结果。整个过程里每一个节点也都是入栈出栈一次时间复杂度O(n)空间复杂度最坏O(n)。注意有些人写中序迭代时会把cur node.right这一步漏掉或者错误地写成在弹栈时修改栈顶节点的右孩子。漏掉这一步会导致循环陷入死循环因为 cur 始终停留在已经访问过的节点上无法推进。正确写法里cur node.right扮演的角色就是递归中“处理完左子树和根节点转向右子树继续递归”的入口。3.3 中序版本对后续学习的帮助中序迭代培养的感觉很重要访问一个“根”节点之前你必须确认它的左子树已经全部完成。这个“确认前置条件”的思路会直接迁移到很多树形问题上比如二叉搜索树中第K小的节点、验证二叉搜索树都需要按中序顺序逐个扫描节点。此时你不需要递归版的中序直接用迭代中序配合计数器就能轻松做到“遍历到第K个节点时提前终止”。而递归版中序很难做到“提前终止后立刻把状态传出去”因为递归调用链已经一层层铺开了。用显式栈则可以把退出条件写得很灵活这也是迭代遍历除了“避免栈溢出”之外的另一个隐藏价值控制权在你手里你可以随时中断可以随时恢复不必把整棵子树全部处理完才回来。4. 后序遍历三种解法从易到难4.1 为什么后序遍历会卡住很多人后序遍历的顺序是“左子树、右子树、根节点”。问题出在根节点上你在访问根节点之前必须先确认左右子树都处理完了。但是在迭代过程中你第一次遇到根节点时它的左右子树还都没有处理你既不能立刻访问它也不能简单地把它丢弃因为等左子树和右子树完成后你还要回到根节点上来。这就产生了一个递归里不存在的问题你需要在栈里记住“我已经处理到哪一步了”。前序和中序都没有这个烦恼因为前序遇到根就先访问中序在左子树处理完后会自然遇到根。唯独后序根是最后收拾的那个。解决这个问题的思路按照从易到难可以分成三种双栈法、prev指针法、状态标记法。每一种都有自己适合的场景下面逐个拆。4.2 解法一双栈法取巧但实用双栈法的洞察来自于前序遍历的对称性。前序遍历顺序是“根左右”如果把压栈顺序从“先右后左”改成“先左后右”得到的访问顺序就变成“根右左”。再把“根右左”整体反转就得到“左右根”恰好是后序遍历。实现时用两个栈。第一个栈负责生成“根右左”的顺序第二个栈负责把顺序反过来def postorder_iter_two_stacks(root): if not root: return [] res [] s1 [root] s2 [] while s1: node s1.pop() s2.append(node.val) if node.left: s1.append(node.left) if node.right: s1.append(node.right) return s2[::-1]这里压栈顺序正好和前端前序写法相反先压左孩子再压右孩子。这样弹出的顺序就是“根、右、左”。弹出的每个值都先放进 s2等到全部结束后s2[::-1]把顺序倒过来得到“左、右、根”。双栈法在理解上特别友好因为不需要思考“什么时候能访问根”你只是先凑出一种顺序再把它整个反转。实践中我不太会为它额外的空间担心多了一个栈只放了值复杂度依然是O(n)。缺点是它和递归过程的对应关系不那么直接如果你想用后序迭代去做某些复杂的回溯逻辑双栈法很难直接改造成更通用的框架。4.3 解法二prev 指针法一次遍历的标准答案prev 指针法不再反转顺序而是直接模拟“系统递归返回”的过程。它维护一个prev变量记录上一次访问的节点用来判断当前栈顶节点是否该被访问。先看代码def postorder_iter_prev(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 and node.right ! prev: cur node.right else: res.append(node.val) prev node stack.pop() return res这段代码里内层循环依然负责“一路向左”压栈。压到不能压之后栈顶就是当前最靠左的、尚未访问的节点。此时分两种情况判断如果这个节点的右孩子存在并且右孩子还没有被访问过说明右子树还没处理那么不能访问这个节点要把 cur 转向它的右孩子继续下一次循环。这里的node.right ! prev是判断“右孩子是否已经被访问过”的关键条件——如果prev正好指向右孩子说明右子树刚刚整体处理完成现在是该处理根节点的时候了。如果右孩子不存在或者右孩子已经访问过了那么左子树和右子树都已经处理完可以弹出并访问当前节点。访问后把prev更新为当前节点再把该节点从栈里弹出。这个“看右孩子是否被访问过”的操作在后序迭代里核心地位很高。你可以把它理解成递归函数返回前要检查的最后两件事左子树是否完成已经靠内层循环保证右子树是否完成靠prev判断。4.4 解法三状态标记法为通用模板铺路状态标记法的想法更直接在栈里多存一个状态位标记这个节点是否已经“处理过右子树”。实现方式很多最直白的一种是每个栈元素存(node, visited)visited为 True 表示“可以访问了”为 False 表示“还在等子树”。以后序为例每次弹出一个 False 的节点就把它的节点本身标记为 True 后压回栈再把右孩子和左孩子压入。这样弹出顺序就会变成“左、右、根”。虽然这个写法会比最简单的前序多几次压栈操作思想上却是最通用的。下一节会专门把它扩展成一套同时覆盖三种遍历的统一模板。这里先不展开代码避免和后面重复。5. 统一模板一套代码吃透三种遍历5.1 模板设计状态标记与压栈顺序的规律如果只记前中后序三个独立的代码很容易混。有没有可能用一套统一的框架只改动入栈顺序就能得到三种遍历答案是肯定的思路就是上一节提到的状态标记法。先明确一个规律栈是后进先出的想要最后输出某个顺序就要按这个顺序的逆序入栈。比如后序的目标顺序是“左、右、根”那么压栈顺序就应该是“根、右、左”。入栈时把根节点标记为“已就绪”弹出时如果遇见已就绪节点就直接输出否则按目标顺序的逆序压栈并把根标记为就绪。这个模板大概是这样的def iter_traversal(root, mode): res [] stack [(root, False)] while stack: node, visited stack.pop() if not node: continue if visited: res.append(node.val) elif mode pre: stack.append((node.right, False)) stack.append((node.left, False)) stack.append((node, True)) elif mode in: stack.append((node.right, False)) stack.append((node, True)) stack.append((node.left, False)) elif mode post: stack.append((node, True)) stack.append((node.right, False)) stack.append((node.left, False)) return res对照代码里的压栈顺序可以看到一个清晰的规律目标访问顺序是什么压栈顺序就是它的反向同时把中间那个“根”标记为 True。前序目标是“根、左、右”压栈顺序是“右、左、根”其中根标记为 True所以依次压入 right、left、node。中序目标是“左、根、右”压栈顺序是“右、根、左”所以依次压入 right、node、left。后序目标是“左、右、根”压栈顺序是“根、右、左”所以依次压入 node、right、left。把三列放一起对照差别一目了然遍历目标访问顺序入栈顺序先到后根节点是否先标记为已访问前序根 → 左 → 右右 → 左 → 根最后一层再标记中序左 → 根 → 右右 → 根 → 左中间层标记后序左 → 右 → 根根 → 右 → 左最先标记5.2 模板法背后的统一性这套模板的优势很明显对于一个需要同时掌握三种遍历的人只需要记住“目标顺序的逆序压栈根节点标记为已访问”这一句话剩下的就是机械填写。它是怎么做到统一的关键在visited标记上。普通的显式栈只管节点本身分不清“这个节点是第一次遇到还是右子树处理完回来的”。模板法用布尔标记把这两种状态显式区分开。弹出时若标记为 True说明时机已经成熟立即输出若标记为 False说明子树还没处理完就按顺序把根、右、左重新压入。这也意味着每个节点会入栈两次一次是作为 False 未处理的节点一次是作为 True 可输出的节点。代价也因此很明显每个节点会经历多次入栈出栈常数开销比前序最简版本大。实际工程里如果只是简单遍历一遍二叉树我更倾向用前序或中序的最简迭代版少折腾。但如果你正在准备面试又怕三种写法记串模板法能显著降低口误和手误的概率。5.3 模板法在面试中的价值面试时我通常建议按“分步策略”来讲。先写递归版本这是基础盘然后针对前序或中序写最简迭代版本展示你对栈的掌握如果被问到后序再引出模板法或者双栈法。不要一上来就甩出状态标记模板那样会显得像是在背代码因为考官更想看到的是你判断“什么时候该用更复杂的标记”的思考过程。模板法还有一个隐藏好处它天然支持“自定义遍历规则的扩展”。比如黎曼遍历、按某种混合顺序处理节点只要改一下入栈顺序就能做到。这在做复杂树形结构的题目时是很好的调试工具。6. 常见问题排查与面试实战心得6.1 高频 Bug 清单你大概率栽在这些地方迭代遍历代码不长但坑却格外多。我见过初学者反复踩过的问题整理成一张速查表问题现象可能原因解决思路前序输出变成“根右左”压栈顺序写反先压了左孩子记忆口诀想先访问谁谁就后入栈中序遍历结果少了一截外层循环只写了while cur改成while cur or stack中序死循环弹出节点后忘了cur node.right每次弹栈访问后必须推进到右子树后序输出变成前序双栈法中 s1 压栈顺序错误确认先压左孩子再压右孩子输出整体反转空树报属性错误没有判断root是否为空函数开头加if not root: return []后序丢节点prev 指针更新位置不对弹出访问后立即更新 prev再把节点弹出每一类问题都有同一个底层教训迭代遍历的每一条语句都在对应递归里的某一个具体动作。理不清这个对应关系只能靠死记理清了出错的概率自然大幅下降。6.2 推荐一个笨但有效的调试方式打印栈调试迭代遍历有个特别适合新手的土办法在关键位置打印栈的内容。别觉得土它比单步调试更直观。你可以在压栈后、弹栈前各加一行输出打印栈里节点的值。这样每跑一次你都能看到栈的状态变化和手跑的样例逐行对上。比如前序遍历时你会看到栈的变化规律是“不断把根弹出去再从右侧补进来”中序遍历时你会看到栈的特点是“左边一路压到底结束后再一层层弹出来”。看多了以后你会对“为什么中序要先压左子树”有一种肌肉记忆比硬背代码可靠得多。另一个实用技巧是在本地准备一棵固定的小树比如上一节那棵五节点树专门用它验证三种遍历的迭代输出。小树节点少手动展开速度快任何时候写新模板都能立刻对照标准输出检查。6.3 面试官问“为什么不用递归”时你应该怎么答面试时遇到二叉树遍历容易紧张回答问题容易背模板。我的建议是先用一句话讲核心“递归隐式使用了系统调用栈迭代遍历是用显式栈模拟这个过程好处是可以控制空间、避免栈溢出而且在需要提前中断或修改遍历顺序时更灵活。”讲前序时重点讲“根先输出所以弹栈就访问右左顺序压栈”。讲中序时重点讲“要先走到最左所以用内层循环压栈再弹栈访问然后转向右子树”。讲后序时如果不打算现场写复杂模板可以用双栈法救场先输出“根右左”再反转成“左右根”。这个解释既简洁又不容易出错。如果面试官接着追问“中间那层栈深度最坏是多少”你还要能答出最坏情况下空间复杂度是O(n)。如果想更出彩可以提一句后续可以利用 Morris 遍历做到 O(1) 空间复杂度但那是锦上添花先把迭代基础打牢比什么都重要。我个人在实际操作中的体会是迭代遍历真正难的地方不是代码而是“把递归在心里拆成一步一步动作”的那种图像感。第一次写后序时我也靠双栈法才稳住了局面写得多了之后再去用 prev 指针法和模板法才逐渐明白每一种写法都是在补同一个缺口——记住“根节点被处理到了哪一步”。如果你正在刷题建议别只背一个版本三种写法至少都要动手敲一遍。第一次会错第二次会慢第三次基本就能做到随手写出来。这个过程没有捷径但跑通了之后后面再做树的深度优先搜索、回溯剪枝你会明显觉得底盘扎实了很多。
