如何在 LeetCode 上使用栈将递归解法转换为迭代

发布: 2天前 (2025年12月8日 GMT+8 11:20)

8 min read

原文: Dev.to

Source: Dev.to

Originally published on LeetCopilot Blog

TL;DR

递归本质上就是函数调用自身，而 调用栈 负责记住局部状态；将递归转为迭代意味着用你自己的显式栈来模拟这个调用栈。

核心步骤

确定递归的状态。
将每一次调用转换为一个栈帧对象。
推入初始帧。
当栈非空时循环。
通过推入新帧来展开子节点。

把递归树和栈并排可视化，能够更直观地看出每个帧需要保存哪些信息。

初学者常常忘记在帧中存储足够的状态（例如，部分结果或当前处理的是哪一个子节点），或者以错误的顺序推入子节点，从而意外改变遍历行为。

通过练习，你可以把递归和迭代视为可互换的工具，在面试官要求给出迭代版本时也能从容应对。

初学者友好的解释：递归到底在做什么

隐藏的栈

每一次递归调用：

在栈帧中保存参数和 局部变量。
跳入函数体内部执行。

当函数返回时，前一个栈帧会在中断的地方继续执行。

可以这样想象：

Call: dfs(root)

Stack (top at bottom):
  [dfs(root)]
    ↳ calls dfs(root.left)
  [dfs(root)]       [dfs(root.left)]
    ↳ calls dfs(root.left.left)
  [dfs(root)] [dfs(root.left)] [dfs(root.left.left)]

当遇到基准情况时，栈帧会一个接一个弹出。

用一句话概括迭代思路

把递归转为迭代，就是自己掌控那个栈——决定每个帧存什么、何时压栈以及在循环中如何处理它们。

步骤化框架：将递归转为迭代

我们以二叉树上的经典递归 DFS 为例进行演示。

步骤 1：编写或检查递归版本

前序遍历（root → left → right）：

def preorder(root):
    if not root:
        return []
    return [root.val] + preorder(root.left) + preorder(root.right)

关键观察

每次调用的状态：root 节点的引用。
访问顺序：先处理当前节点，然后左子节点，最后右子节点。

步骤 2：决定“栈帧”要保存什么

对于这个简单的 DFS，帧只需要：

节点本身。

在更复杂的递归中，帧可能需要：

节点 + 部分结果。
节点 + 正在处理的子节点索引。
其他参数，如剩余目标和、深度等。

步骤 3：像第一次调用一样初始化栈

递归的第一次调用是 preorder(root)，所以迭代版的初始栈应当模拟这一点：

type Frame = { node: TreeNode | null };

将 { node: root } 推入栈中即可开始。

步骤 4：在栈非空时循环

取代调用栈的，是你自己控制的循环：

function preorderIterative(root: TreeNode | null): number[] {
  const result: number[] = [];
  if (!root) return result;

  const stack: TreeNode[] = [root]; // 这里的帧可以直接用节点表示

  while (stack.length > 0) {
    const node = stack.pop()!;
    result.push(node.val);

    // 逆序压入子节点（栈是 LIFO）
    if (node.right) stack.push(node.right);
    if (node.left)  stack.push(node.left);
  }

  return result;
}

push 的顺序保证了 root → left → right：先压入 right 再压入 left，弹出时会先处理 left。

可视化对比：递归 vs 迭代

递归 DFS（前序）

Call stack (top at bottom):

preorder(A)
  preorder(B)
    preorder(D)
    preorder(E)
  preorder(C)
    preorder(F)

使用栈的迭代 DFS

Initial: stack = [A]

Pop A → visit A → push C, B      stack = [C, B]
Pop B → visit B → push E, D      stack = [C, E, D]
Pop D → visit D                  stack = [C, E]
Pop E → visit E                  stack = [C]
Pop C → visit C → push F         stack = [F]
Pop F → visit F                  stack = []

访问顺序保持一致：A, B, D, E, C, F。

更复杂的情况：用显式状态模拟“后序”

有些递归函数会在处理完子节点后再做工作（例如后序遍历或树形 DP）。这时每个帧需要额外的状态。

递归后序

def postorder(root):
    if not root:
        return []
    return postorder(root.left) + postorder(root.right) + [root.val]

带 visited 标记的迭代版本

type Frame = {
  node: TreeNode;
  visited: boolean; // 是否已经压入过子节点？
};

function postorderIterative(root: TreeNode | null): number[] {
  const result: number[] = [];
  if (!root) return result;

  const stack: Frame[] = [{ node: root, visited: false }];

  while (stack.length > 0) {
    const frame = stack.pop()!;
    const { node, visited } = frame;

    if (visited) {
      // 子节点已处理完，现在处理当前节点
      result.push(node.val);
    } else {
      // 后序：左、右、根
      // 先把当前节点重新压入，标记为已访问
      stack.push({ node, visited: true });
      if (node.right) stack.push({ node: node.right, visited: false });
      if (node.left)  stack.push({ node: node.left, visited: false });
    }
  }

  return result;
}

这种 重新压入并加标记 的模式，是在不使用递归的情况下模拟“子节点处理完后再做事”的强大技巧。

实战准备策略

策略 1：练习树的 DFS 各种变体

从以下顺序开始：

前序（根–左–右）。
中序（左–根–右）。
后序（左–右–根）。

对每一种：

编写递归版本。
确定每次调用的状态。
用栈帧对象实现迭代版本。

这样可以为更复杂的转换打下坚实基础。

策略 2：每周改写一个真实的 LeetCode 题目

挑选一个已经写好的递归解法，按照以下步骤：

为一个小例子画出递归树。
标注每个帧需要记住的内容。
用栈帧对象写出对应的迭代实现。

把这种模式记录在笔记或 DSA 学习路径中，面试前可以快速回顾。

策略 3：使用可视化工具排查卡点

当你的迭代实现与递归结果不一致时，利用 LeetCopilot 等工具同步步进两种实现，观察栈的变化，帮助你精准定位模拟偏差的地方。

常见错误需避免

错误 1：帧中未存足够的状态

（…文章后续还有更多错误说明…）