LeetCode 94. 中序遍历的迭代实现：显式栈与「递归的展开」

为什么要有迭代版

递归中序遍历三行代码：traverse(left); visit(root); traverse(right)——「递归栈」替你保存了「回溯的位置」——「迭代版」需要自己管理这个栈——「为什么写迭代版」的三个理由：一、深树的栈溢出（链状树（每个节点只有右孩子）递归深度 n——「10 万节点」的递归栈爆——Python 的默认递归限——「工程的真实风险」——「栈空间」的显式控制（堆上分配——「显式栈」突破递归限制。二、控制流的中断（「遍历的暂停与恢复」（生成器、惰性求值——「递归无法暂停」——「迭代器」的形态——「遍历即迭代器」的设计（「无限遍历」的流式处理——三、性能的极致（「递归的调用开销」（函数调用的栈帧——「迭代」的零调用开销——**「极致优化」的场景。

中序的迭代实现

「一路向左、弹栈右转」的算法：「迭代的动作分解」：「当前节点的左子树还没遍历完时，当前节点不能访问」——中序的语义（左-根-右——「栈保存『还没访问但迟早要访问』的节点」——**「栈中的节点 = 左子树处理中的祖先」：

def inorder_traversal(root):
    stack, res = [], []
    curr = root
    while stack or curr:
        while curr:              # 1. 一路向左压栈
            stack.append(curr)
            curr = curr.left
        curr = stack.pop()       # 2. 弹栈访问（最左）
        res.append(curr.val)     # 3. 访问
        curr = curr.right        # 4. 转向右子树
    return res

「循环不变量」的理解：「栈顶节点 = 下一个该访问的节点」——「curr = 该节点左子树的最左」或「某节点的右子树起点」——「两种状态的交替」——「手动追踪一遍」（[1,2,3] 树，root=2，left=1，right=3）：curr=2 压栈 → curr=1 压栈 → curr=None → 弹 1 访问 → curr=1.right=None → 弹 2 访问 → curr=3 → 3 压栈 → curr=None → 弹 3 访问——「1,2,3」——中序 ✓——「追踪验证」的方法在迭代中更重要（递归靠信任、迭代靠追踪）。

「前序的迭代」（对比）：「前序的处理时机在进入时」——「弹栈即访问」：出栈访问、先右后左压栈（「先右后左」的原因（栈的后进先出——先压右、后压左——左先处理——「前序迭代的简洁」（访问与入栈都在弹栈时——「前序迭代的直觉性」高于中序——「三种遍历的迭代难度排序」：前序最简单、中序中等、后序最复杂（「后序需要『知道右子树访问完了』」——「上一个访问的节点」的判断（「后序的双栈法与单栈法」——单栈法（记录 last visited——「右子树访问完才访问根」的判断——「prev 指针」（「后序迭代的复杂度」是三者之最——**「理解了后序迭代，才算真正理解显式栈模拟」。

「递归的显式化」的通用方法

「模拟递归栈帧」的思路：递归栈帧 =（节点 + 状态）——「状态」的显式编码（「节点该做哪一步了」——「栈元素带状态标记」：(node, visited_flag)——「弹栈时看标记」（未访问=压右子树、标记访问、压自身——「状态机」的栈模拟——「通用模板」：任何递归都可以用「节点+状态」的栈元素改写——「通用性」的代价（代码复杂度——「专用迭代」优于「通用模拟」（中序的专用写法更简洁——「通用模板」是理解工具、「专用写法」是生产工具——「两者都懂、按需使用」。「递归改迭代的判定」：「什么时候值得改」：递归深度不可控（用户数据驱动树的形状——「恶意的链状输入」（攻击者构造 10 万层深的树——「栈溢出」的 DoS——「安全视角」的迭代化动机——「深度不受控 = 迭代化」的工程纪律——「递归的深度」与「数据的安全性」。

工程中的真实意义

「深树」的真实场景：「表达式树」（编译器的语法树（「深层嵌套表达式」（一万个括号嵌套——「语法树的深度」——「编译器的迭代遍历」——「AST 遍历」的工程实践——「JSON 的深层嵌套」（「JSON 解析器的栈」（递归下降解析器的深度——「一万个嵌套数组」的 JSON——「解析器的迭代化」——「深数据」在工程中真实存在。「显式栈的工程价值」：「栈的大小」可控（堆分配——「栈溢出」从「致命」变「可处理」——「可恢复的错误」——「显式栈」的容错——「遍历的暂停恢复」（分页遍历（「每次取一批」——「遍历的分布式」（「遍历的状态」可序列化——「迭代器」的分布式遍历。「性能的真相」：「迭代不一定更快」（显式栈的开销 vs 递归栈的优化（现代编译器的尾递归优化——「Python 没有尾递归优化」——「尾递归」的语言差异——「迭代的动机」是安全与控制、不是速度——「性能」的误解澄清。中序迭代的进阶总结：显式栈模拟递归（一路向左压栈、弹栈右转）+「节点+状态」的通用模拟 +迭代化的工程意义（深树栈溢出的防御、遍历的暂停恢复、恶意输入的安全）——「递归改迭代」不是炫技，是「当递归的深度由数据决定时」的工程必须——「栈深度」从系统的不可控变成你的可控——**「控制权」的转移，就是迭代的真正价值

优雅停机高频问答

收尾前回答两个高频问题。「kill -9 的时候全都没用了怎么办？」——SIGKILL 的场景：「SIGKILL 的来源」：K8s 的 grace period 超时——「grace period 的调大」（terminationGracePeriodSeconds——「超时的原因」（存量请求处理慢——「SIGKILL 的兜底逻辑」（应用层的崩溃恢复——「重启后的恢复」（消息重复、状态丢失——「幂等与状态外置」的保险——「SIGKILL 是常态化的假设」——「应用假设随时可能被杀」——「crash-safe」的设计（随时挂都能恢复。「发布时能不能不停机？」——不能完全避免但可最小化：「零停机」的极限：蓝绿发布的切换（「蓝绿」的切换瞬间（切换的原子性——「蓝绿 vs 滚动」的选择——「折损的最小化」（优雅停机+滚动串行——「零停机」的定义（用户无感——「无感」是目标不是承诺。优雅停机的问答收束：优雅停机的三个心智模型——「摘流量是关门（不再接客）、处理存量是送客（送走现有客人）、SIGKILL 是拆迁（突然断电）」——「关门→送客→才拆迁」的顺序——「拆迁随时可能来」——所以「状态外置+幂等」是拆迁保险——「优雅停机的练习」：每次发版都按流程走——「流程的肌肉记忆」靠每次发版的执行。

统一迭代法与 Morris 遍历：迭代实现的两个高级形态

正文讲了中序的「专用迭代」，这里补两个更成体系的高级形态。「统一迭代法（颜色标记法）」：三种遍历各背一套栈写法太重，统一法的思路是把递归栈帧「显式化到极致」——栈里存的不是裸节点，而是「(节点, 访问状态)」二元组：第一次出栈时若未访问，就按「遍历顺序的反序」重新压栈——中序的压入次序是：右孩子（白）、自己（灰）、左孩子（白）；出栈遇灰色才真正访问。三种遍历共用这一个模板，只改三行的入栈顺序——白节点代表「还有子树没处理」、灰节点代表「左右已就位、轮到我输出」，这与递归栈帧里「执行到哪一行」的状态编码完全同构。它的价值不在性能（常数比专用写法差），在于一个模板覆盖三种遍历——面试时忘了中序专用写法，统一法是可靠的兜底，也是理解「递归即栈状态机」的教具。「Morris 遍历」：把空间压到 O(1) 的黑科技——不用栈、不用队列，靠临时借用叶子的空右指针回溯：访问节点 cur 时，先找它左子树的最右节点（中序前驱），把前驱的 right 指回 cur（建「线索」），cur 左移；等再次走到 cur 时（经由线索），说明左子树已遍历完，访问 cur、拆掉线索、右移。整棵树没有额外内存，代价是每条边最多被走两次（建线索一次、拆线索一次），时间仍是 O(n)。它的适用边界要说清楚：Morris 会临时修改树结构——并发遍历同一棵树、或者只读场景（遍历中不允许写内存）都不适用；工程代码里它也确实少见——可读性差、副作用隐蔽，多数团队宁可多花 O(h) 空间换可维护性。「N 叉树的迭代」顺手一提：二叉的「先右后左压栈」推广成「孩子列表逆序压栈」，层序则原封不动换 BFS——迭代骨架是跨结构通用的。「什么时候值得上这些高级形态」的判断标准反而朴素：默认写递归；深度由不可信输入决定（用户构造的深数据、反序列化外部长度）时换显式栈；空间被严格限制或流式只读时才考虑 Morris——技术选型的顺序是「递归 → 显式栈 → 统一法 → Morris」，越往右越罕见，把罕见武器当默认武器，是新手最常见的炫技式过拟合。最后回应正文那句「迭代的动机是安全与控制」：统一法给了你控制（暂停、恢复、分布式续跑都落在「可序列化的栈状态」上），Morris 给了你极限（内存为零）——而这两个能力，递归都给不了。

「迭代版写错了怎么快速定位？」——给一份高频 bug 清单与排查法。bug 一：while 条件写成 while stack——丢掉了「栈空但 curr 还有右子树」的收尾阶段，序列在根节点处截断；正确条件是「栈非空或 curr 非空」，二者满足其一就继续。bug 二：弹栈访问后忘了转向右子树——curr = curr.right 漏写，下一轮循环拿到的还是旧状态，死循环或重复访问；弹栈、访问、右转是三连动作，一个都不能少。bug 三：统一法的入栈顺序写成正序——栈是后进先出，输出顺序与入栈顺序相反，想要「左-根-右」就必须按「右-根-左」压入——把这个「反序」记成口诀，统一法就不会错。排查的通用手段是正文提过的手动追踪：拿一棵三层的满二叉树，在纸上把栈的内容、curr 的指向逐步画出来——迭代代码的每一步都摆在明面上，追踪十行就能定位任何逻辑错——这也正是迭代版相对递归版的隐性优势：状态全部显式，调试不需要想象递归栈。