算法 - 14. 迭代式DFS (使用栈的树遍历)
algorithmstreetraversalstackiteration
By sko•10/9/2025•35 min read
何时使用迭代式DFS
当需要不使用递归遍历树或图时使用迭代式DFS。虽然最常用于避免深层树的栈溢出,但它也可以适用于:
- 二叉树遍历(中序、前序、后序) - 经典用例
- 当递归深度可能超过限制时的图探索
- 状态空间搜索 - 探索问题的所有可能配置或状态
- 拼图求解(8拼图、魔方、数独)
- 游戏状态探索(国际象棋走法、井字游戏结果)
- 带约束的路径查找(带钥匙/门的迷宫)
- 配置问题(可满足性、约束满足)
- 显式栈使您能够完全看到搜索路径,允许您跟踪访问过的状态、实现自定义剪枝策略,或在找到目标状态时提取实际解决路径
- 需要对栈进行细粒度控制的回溯问题
- 具有受控内存使用的树序列化/反序列化
- 在树/图中查找路径同时维护确切路径
- 任何需要暂停、恢复或检查调用栈的遍历
示例问题
可暂停的文件系统搜索: 您正在为云存储系统构建文件搜索功能,该系统有数百万个文件组织在深层文件夹树中。搜索需要:
- 查找与模式匹配的所有文件(例如: "*.pdf")
- 每1000个文件暂停一次以更新进度条并检查用户是否取消
- 如果用户想要继续,从中断的地方精确恢复
- 为每个匹配的文件返回完整路径
- 避免栈溢出在深度嵌套的文件夹上(数千层深)
假设有这样的文件夹结构:
Root/
├── Documents/
│ ├── reports/
│ │ ├── report1.pdf ✓ 匹配
│ │ └── data.txt
│ └── archive/
│ └── old.pdf ✓ 匹配
└── Downloads/
└── ebook.pdf ✓ 匹配为什么递归不起作用:
- 无法在递归中暂停 - 递归调用会阻塞直到完成
- 无法检查当前路径 - 调用栈是隐藏的
- 栈溢出风险 - 深度嵌套的文件夹会耗尽内存
- 无法恢复 - 如果中断必须从头开始
答案: 迭代式DFS为您提供一个显式栈,可以暂停、检查(以构建文件路径)和恢复 - 这在递归的隐藏调用栈中是不可能的。
迭代式DFS实际做什么
迭代式DFS 使用数据结构(通常是栈)显式模拟递归调用栈。我们不依赖系统的调用栈进行递归,而是手动管理我们自己的栈来控制遍历顺序。
把它想象成搜索文件柜:
- 递归式DFS: 跟随在你身后消失的面包屑 - 你只能看到你现在在哪里,看不到你去过哪里或还有什么要探索的。如果你需要停止,你会失去所有进展。
- 迭代式DFS: 拥有可见的书签列表 - 你可以确切地看到还有哪些文件夹要搜索,随时暂停,检查你的进度,并稍后从完全相同的位置恢复
栈操作的工作原理
核心模式 - "手动管理调用栈"
使用栈遍历时:
-
Push 将节点推入栈(像进行递归调用)
- 保存节点以供以后探索
- 顺序很重要: 最后推入的最先处理(LIFO)
-
Pop 从栈中弹出节点(像从递归调用返回)
- 检索下一个要处理的节点
- 模拟在探索子树后"返回"
-
Process 在正确的时刻处理节点(取决于遍历顺序)
- 前序: 第一次遇到时立即处理(在推入子节点之前)
- 中序: 无法再向左走时处理(在左右探索之间)
- 后序: 仅在两个子节点都完成后处理(第二次访问时)
- 文件搜索: 弹出时处理(检查是否匹配模式)
-
如果需要,跟踪状态(用于复杂遍历)
- 后序: 需要"已访问"标志以知道这是第一次还是第二次访问
- 文件搜索: 通过在栈中存储
[node, path]对来跟踪完整路径 - 图遍历: 跟踪已访问节点以避免循环
- 可暂停搜索: 跟踪进度计数、批次限制、完成状态
三种经典树遍历
中序遍历 - "左、根、右"
处理模式:
- 尽可能向左走(将节点推入栈)
- 无法再向左走时,处理当前节点
- 然后探索右子树
- 重复直到栈为空
前序遍历 - "根、左、右"
处理模式:
- 访问时立即处理节点
- 推入右子节点以供稍后处理(如果存在)
- 移动到左子节点
- 当没有左子节点时,从栈中弹出
后序遍历 - "左、右、根"
处理模式:
- 跟踪是否已访问子节点
- 第一次访问: 将子节点推入栈
- 第二次访问: 处理节点
- 三种模式中最复杂的
这些模式何时应用
这些模式直接映射到许多现实世界场景:
// 前序: 在子节点之前处理父节点(自上而下)
// 示例: 复制树、序列化结构
// 中序: 按排序顺序处理(对于BST)
// 示例: 获取排序值、范围查询
// 后序: 在父节点之前处理子节点(自下而上)
// 示例: 计算大小、删除节点、评估表达式迭代式DFS的美妙之处在于您对遍历有完全控制 - 您可以暂停、检查栈或在执行过程中修改遍历策略!
最重要的洞察
用显式栈操作替换递归调用,其中推入模拟调用,弹出模拟返回 - 通过仔细控制相对于栈操作何时处理节点,我们可以在不使用递归的情况下实现任何遍历顺序。
心智笔记: 算法的天才之处在于维护一个简单的"待办事项列表"来探索节点。栈就是那个列表。在每一步,你从列表中抓取下一项(弹出),对其进行工作,并将你发现的任何新项目添加到列表中(推入)。这个直接的心智模型 - "处理待办事项列表" - 比思考递归更简单,并且自然地为您提供暂停、检查进度或跟踪递归无法提供的自定义状态的控制。
决策框架
在每次迭代时,您会问简单的问题来决定下一步做什么。这是我们文件搜索示例的模式:
文件搜索决策流程(最简单的模式):
从栈中弹出下一项
↓
是文件还是文件夹?
↓
┌───────────────┬───────────────┐
│ 文件 │ 文件夹 │
└───────────────┴───────────────┘
↓ ↓
是否匹配? 将子节点添加
↓ 到栈中
如果是则保存 ↓
↓ 继续循环
继续循环每一步的问题:
- "我应该暂停吗?" → 检查是否已处理足够的节点
- "这是文件还是文件夹?" → 决定要做什么
- "是否匹配模式?" → 仅对文件
- "要探索哪些子节点?" → 将它们推入栈
对于经典树遍历,模式根据您想要处理节点的时间而变化:
前序(处理节点 → 探索子节点):
访问节点
↓
立即处理(收集值)
↓
推入右子节点(稍后保存)
↓
移动到左子节点(立即探索)用例: 复制树结构、序列化数据
中序(探索左 → 处理节点 → 探索右):
能向左走吗?
↓
┌─────是─────┬─────否─────┐
│ │ │
推入当前 弹出并处理
向左走 然后向右走用例: 从BST获取排序值
后序(探索子节点 → 处理节点):
第一次访问节点?
↓
┌─────是─────┬─────否─────┐
│ │ │
推入节点 立即处理
(标记已访问) (子节点完成)
推入子节点用例: 计算树大小、删除节点
核心决策: 每次遍历都归结为"相对于探索其子节点,我何时处理这个节点?"显式栈让您精确控制这个时机。
代码
让我们用实际示例探索所有三种遍历类型。关键区别在于相对于探索其子节点,我们何时处理每个节点。
前序遍历: 处理 → 探索
模式: 在探索子节点之前处理当前节点 用例: 搜索、复制树、前缀表达式求值
// 用于演示的简单二叉树节点
type TreeNode = {
val: number;
left: TreeNode | null;
right: TreeNode | null;
};
// === 前序: 在子节点之前处理节点 ===
function preorderIterative(root: TreeNode | null): Array<number> {
if (root == null) return [];
const result: Array<number> = [];
const stack: Array<TreeNode> = [root];
while (stack.length > 0) {
const node = stack.pop();
if (node == null) continue;
// 决策框架: 看到节点时立即处理
result.push(node.val); // 首先处理父节点
// 然后添加子节点供将来探索
// 先推入右节点,这样左节点先被处理(LIFO)
if (node.right) stack.push(node.right);
if (node.left) stack.push(node.left);
}
return result;
}
// 示例树: 1
// / \
// 2 3
// / \
// 4 5
// 前序: [1, 2, 4, 5, 3] (根 → 左 → 右)现实示例: 文件系统搜索
// 文件系统节点的定义
class FileNode {
name: string;
isFile: boolean;
children: Array<FileNode>;
constructor(
name: string,
isFile: boolean = false,
children: Array<FileNode> = []
) {
this.name = name;
this.isFile = isFile;
this.children = children; // FileNode数组(如果isFile为true则为空)
}
}
// 搜索结果和进度的类型定义
type SearchStatus = "paused" | "complete" | "already_complete";
type PausedSearchResult = {
status: "paused";
processed: number;
matches: number;
stackDepth: number;
};
type CompleteSearchResult = {
status: "complete" | "already_complete";
processed: number;
matches: number;
results: Array<string>;
};
type SearchResult = PausedSearchResult | CompleteSearchResult;
type ProgressInfo = {
nodesProcessed: number;
matchesFound: number;
remainingInStack: number;
isComplete: boolean;
};
// 栈条目类型: 具有节点及其从根的完整路径的对象
type StackEntry = {
node: FileNode;
path: string; // 从根的完整路径(例如: "Root/Documents/reports")
};
// === 可暂停文件搜索 ===
// 搜索与模式匹配的文件,具有暂停和恢复能力
// 使用前序遍历: 在探索其子节点之前处理每个节点
class PausableFileSearch {
private root: FileNode;
private pattern: string;
private searchStack: Array<StackEntry>;
private matchingFiles: Array<string>;
private totalNodesProcessed: number;
private isComplete: boolean;
constructor(root: FileNode, pattern: string) {
this.root = root;
this.pattern = pattern;
// 显式栈存储具有节点及其从根的完整路径的对象
// 最初,根的路径只是其名称
this.searchStack = [{ node: root, path: root.name }];
// 搜索结果和进度跟踪
this.matchingFiles = [];
this.totalNodesProcessed = 0;
this.isComplete = false;
}
// 遍历树,处理节点并扩展到子节点
// 继续直到达到节点限制或完成遍历
traverse(nodeLimit: number = 1000): SearchResult {
let nodesProcessedThisCall = 0;
while (true) {
// 决策框架: 遍历完成了吗?
const isStackEmpty = this.searchStack.length === 0;
if (isStackEmpty) {
// 没有更多节点要探索 - 搜索完成
this.isComplete = true;
return {
status: "complete",
processed: this.totalNodesProcessed,
matches: this.matchingFiles.length,
results: this.matchingFiles,
};
}
// 决策框架: 我们应该暂停吗?
const shouldPause = nodesProcessedThisCall >= nodeLimit;
if (shouldPause) {
// 在这里暂停 - 栈保留我们的确切位置
return {
status: "paused",
processed: this.totalNodesProcessed,
matches: this.matchingFiles.length,
stackDepth: this.searchStack.length,
};
}
// 从栈中弹出下一个节点及其完整路径
// 我们已经在上面验证栈不为空
const stackEntry = this.searchStack.pop();
// 由于上面的非空检查,这永远不应该发生,
// 但TypeScript不理解控制流
if (stackEntry == null) {
throw new Error("Unexpected: stack was empty after non-empty check");
}
const currentNode = stackEntry.node;
const currentPath = stackEntry.path;
nodesProcessedThisCall++;
this.totalNodesProcessed++;
// 前序: 在探索子节点之前处理当前节点
// 决策框架: 这是文件还是文件夹?
if (currentNode.isFile) {
// 检查文件是否匹配模式
const matchesPattern = currentNode.name.endsWith(this.pattern);
if (matchesPattern) {
this.matchingFiles.push(currentPath);
}
} else {
// 它是文件夹 - 添加子节点到栈供将来探索
// 这发生在处理当前节点之后(前序)
// 以相反顺序推入,这样我们从左到右处理
const children = currentNode.children;
for (let i = children.length - 1; i >= 0; i--) {
const childNode = children[i];
const childPath = `${currentPath}/${childNode.name}`;
// 推入带有完整路径的子节点
this.searchStack.push({ node: childNode, path: childPath });
}
}
}
}
// 从暂停处恢复遍历
resume(nodeLimit: number = 1000): SearchResult {
const canResume = !this.isComplete && this.searchStack.length > 0;
if (canResume) {
return this.traverse(nodeLimit);
}
return {
status: "already_complete",
processed: this.totalNodesProcessed,
matches: this.matchingFiles.length,
results: this.matchingFiles,
};
}
// 获取当前进度
getProgress(): ProgressInfo {
return {
nodesProcessed: this.totalNodesProcessed,
matchesFound: this.matchingFiles.length,
remainingInStack: this.searchStack.length,
isComplete: this.isComplete,
};
}
}
// === 使用示例: 文件系统搜索 ===
// 从示例构建文件系统树
const fileSystem = new FileNode("Root", false, [
new FileNode("Documents", false, [
new FileNode("reports", false, [
new FileNode("report1.pdf", true),
new FileNode("data.txt", true),
]),
new FileNode("archive", false, [new FileNode("old.pdf", true)]),
]),
new FileNode("Downloads", false, [new FileNode("ebook.pdf", true)]),
]);
// 创建PDF文件搜索
const search = new PausableFileSearch(fileSystem, ".pdf");
// 第一次遍历: 处理2个节点然后暂停
let result = search.traverse(2);
console.log(`状态: ${result.status}`);
console.log(`已处理: ${result.processed} 个节点`);
console.log(`找到匹配: ${result.matches}`);
// 暂停结果的类型守卫
if (result.status === "paused") {
console.log(`栈深度: ${result.stackDepth} (可以从这里恢复)`);
}
// 检查进度
console.log(search.getProgress());
// 恢复: 再遍历3个节点然后暂停
result = search.resume(3);
console.log(`状态: ${result.status}`);
console.log(`总共已处理: ${result.processed} 个节点`);
console.log(`找到匹配: ${result.matches}`);
// 恢复直到完成
result = search.resume(1000);
console.log(`状态: ${result.status}`);
console.log(`总共处理的节点: ${result.processed}`);
console.log(`总匹配数: ${result.matches}`);
// 完成结果的类型守卫
if (result.status === "complete" || result.status === "already_complete") {
console.log("\n匹配的文件:");
result.results.forEach((path) => console.log(` ${path}`));
}中序遍历: 探索左 → 处理 → 探索右
模式: 在探索左右子节点之间处理节点 用例: 二叉搜索树(给出排序输出)、表达式树
// === 中序: 在子节点之间处理节点 ===
function inorderIterative(root: TreeNode | null): Array<number> {
if (root == null) return [];
const result: Array<number> = [];
const stack: Array<TreeNode> = [];
let current: TreeNode | null = root;
// 使处理显式的辅助函数
function processNode(value: number) {
result.push(value); // 或其他逻辑
}
while (current != null || stack.length > 0) {
// 决策框架: 首先尽可能向左走
while (current != null) {
stack.push(current); // 栈操作: 保存以供稍后使用
current = current.left;
}
// 当无法再向左走时处理节点
const node = stack.pop(); // 栈操作: 检索保存的节点
if (node != null) {
processNode(node.val); // 在左右之间处理(不是栈操作)
current = node.right; // 现在探索右子树
}
}
return result;
}
// 示例BST: 4
// / \
// 2 6
// / \ / \
// 1 3 5 7
// 中序: [1, 2, 3, 4, 5, 6, 7] (已排序!)现实示例: 数据库索引遍历
我们在做什么: 假设您有一个包含用户记录的数据库表,并且您想要按姓名的字母顺序检索所有用户。数据库不是扫描整个表并排序,而是使用二叉搜索树(BST)索引来组织姓名。
问题: 给定"name"列上的BST索引,按字母顺序检索所有用户记录。
示例数据库表 (Users):
| Record ID | Name | Email | | --------- | ------- | --------------- | | 101 | Charlie | charlie@ex.com | | 102 | Alice | alice@ex.com | | 103 | David | david@ex.com | | 104 | Bob | bob@ex.com | | 105 | Alice | alice2@ex.com |
在"Name"列上构建的索引树:
"Charlie" → [101]
/ \
"Alice" → [102,105] "David" → [103]
\
"Bob" → [104]每个节点存储:
- key: 姓名(索引值)
- recordIds: 具有该姓名的行ID数组(例如: 两个Alice: 行102和105)
目标: 使用中序遍历按字母顺序获取所有姓名: Alice → Bob → Charlie → David
// 用于数据库索引的二叉搜索树
class IndexNode {
key: string; // 索引值(例如: 用户名"Alice")
recordIds: Array<number>; // 具有此键值的所有数据库行的ID
left: IndexNode | null = null;
right: IndexNode | null = null;
constructor(key: string, recordId: number) {
this.key = key;
this.recordIds = [recordId]; // 最初包含一个记录ID
}
}
// 按字母顺序查找所有记录
// root: 已构建的BST索引的根
// 返回: 按字母顺序从姓名到记录ID的映射
function getAllRecordsInOrder(
root: IndexNode | null // BST已经通过结构维护排序顺序
): Map<string, Array<number>> {
const orderedRecords = new Map<string, Array<number>>();
const stack: Array<IndexNode> = [];
let current = root;
while (current != null || stack.length > 0) {
// 导航到最左边的节点
while (current != null) {
stack.push(current);
current = current.left;
}
// 处理节点(按排序顺序)
const node = stack.pop();
if (node != null) {
orderedRecords.set(node.key, node.recordIds);
current = node.right;
}
}
return orderedRecords;
}
// 姓名的示例索引树:
// "Charlie"
// / \
// "Alice" "David"
// \
// "Bob"
//
// 中序遍历给出: Alice → Bob → Charlie → David (字母顺序!)后序遍历: 探索 → 处理
模式: 在探索所有子节点后处理节点 用例: 计算大小、删除树、后缀表达式求值
// === 后序: 在子节点之后处理节点 ===
function postorderIterative(root: TreeNode | null): Array<number> {
if (root == null) return [];
const result: Array<number> = [];
const stack: Array<{ node: TreeNode; visited: boolean }> = [
{ node: root, visited: false },
];
while (stack.length > 0) {
const entry = stack[stack.length - 1]; // 查看顶部
// 决策框架: 我们是否已经访问过这个节点的子节点?
if (!entry.visited) {
// 第一次看到这个节点 - 标记为已访问并添加子节点
entry.visited = true;
// 添加子节点(先右后左,这样左先被处理)
if (entry.node.right) {
stack.push({ node: entry.node.right, visited: false });
}
if (entry.node.left) {
stack.push({ node: entry.node.left, visited: false });
}
} else {
// 第二次看到这个节点 - 子节点完成,处理它
stack.pop();
result.push(entry.node.val); // 在子节点之后处理
}
}
return result;
}
// 示例树: 1
// / \
// 2 3
// / \
// 4 5
// 后序: [4, 5, 2, 3, 1] (左 → 右 → 根)现实示例: 计算目录大小
// 具有大小的文件系统节点
class FileSystemNode {
name: string;
isFile: boolean;
size: number; // 对于文件: 实际大小。对于目录: 从子节点计算
children: Array<FileSystemNode>;
constructor(name: string, isFile: boolean, size: number = 0) {
this.name = name;
this.isFile = isFile;
this.size = size;
this.children = [];
}
}
// 计算每个目录的总大小(必须先处理子节点!)
function calculateDirectorySizes(root: FileSystemNode): Map<string, number> {
const directorySizes = new Map<string, number>();
const stack: Array<{
node: FileSystemNode;
path: string;
visited: boolean;
}> = [{ node: root, path: root.name, visited: false }];
while (stack.length > 0) {
const entry = stack[stack.length - 1];
if (!entry.visited) {
// 第一次访问: 添加子节点到栈
entry.visited = true;
if (!entry.node.isFile) {
// 添加所有子节点供处理
for (const child of entry.node.children) {
stack.push({
node: child,
path: `${entry.path}/${child.name}`,
visited: false,
});
}
}
} else {
// 第二次访问: 子节点已处理,计算此节点的大小
stack.pop();
if (entry.node.isFile) {
// 文件: 只使用其大小
// 父目录将汇总此值
} else {
// 目录: 汇总所有子节点的大小
let totalSize = 0;
for (const child of entry.node.children) {
if (child.isFile) {
// 文件: 使用文件的直接大小
totalSize += child.size;
} else {
// 子目录: 检索已计算的总数
// 后序保证此子目录已完全处理
// 之前(在其父节点之前从栈中弹出),因此其完整
// 大小已存储在映射中。我们不是重复计算 -
// 我们使用预计算的总数而不是重新计算。
const childPath = `${entry.path}/${child.name}`;
const childDirectoryTotal = directorySizes.get(childPath) || 0;
totalSize += childDirectoryTotal;
}
}
// 在映射中存储此目录的总大小
// (当此目录作为子节点出现时将使用此总数)
directorySizes.set(entry.path, totalSize);
entry.node.size = totalSize; // 更新节点本身
}
}
}
return directorySizes;
}
// 示例文件系统:
// Root/
// ├── docs/ (总共30KB)
// │ ├── file1.txt (10KB)
// │ └── file2.txt (20KB)
// └── images/ (总共150KB)
// ├── pic1.jpg (100KB)
// └── pic2.jpg (50KB)
//
// 后序确保我们计算docs/和images/的大小
// 在计算Root/大小(180KB)之前总结: 何时使用每种遍历
| 遍历 | 何时处理 | 用例 | | ---------- | -------------------- | -------------------------------------------- | | 前序 | 在子节点之前 | 搜索、复制、序列化 | | 中序 | 在左右之间 | 从BST排序检索 | | 后序 | 在所有子节点之后 | 大小计算、清理、依赖关系 |
迭代式DFS的美妙之处在于,通过显式管理栈,您可以完全控制遍历顺序 - 只需更改相对于探索子节点时处理节点的时机!
疑问解答
常见疑问: "迭代式DFS真的能处理递归式DFS能做的所有事情吗? 更广泛地说,迭代能替代所有递归逻辑吗,不仅仅是DFS? 还是有些情况递归是根本必要的?"
基本等价性: 迭代能替代所有递归吗?
是的,理论上任何递归算法都可以转换为迭代算法。 这不是DFS特有的 - 这是计算机科学的基本原理。
为什么这普遍成立: 每个递归算法都使用调用栈。迭代版本只是使用显式栈数据结构。由于您始终可以创建自己的栈,因此您始终可以用迭代替换递归。
这适用于所有递归算法:
- 树/图遍历 (DFS、BFS变体)
- 分治 (快速排序、归并排序、二分搜索)
- 回溯 (N皇后、数独求解器、排列)
- 动态规划 (可以是自上而下递归或自下而上迭代)
- 数学递归 (斐波那契、阶乘、汉诺塔)
对于DFS具体而言,等价性之所以有效的原因如下:
当您进行递归调用时,系统自动执行两件事:
- 保存局部变量 到调用栈
- 记住返回位置 当调用完成时
使用迭代式DFS,您手动执行这两件事:
- 保存状态 在显式栈中(在栈条目中存储变量)
- 控制执行流 使用循环和栈操作
通过示例证明 - 这是一个递归函数及其迭代等价物:
// 递归: 计算树高
function heightRecursive(node: TreeNode | null): number {
if (node == null) return 0;
// 递归调用将这些计算保存在调用栈上
const leftHeight = heightRecursive(node.left);
const rightHeight = heightRecursive(node.right);
return Math.max(leftHeight, rightHeight) + 1;
}
// 迭代: 相同的计算,显式栈
function heightIterative(root: TreeNode | null): number {
if (root == null) return 0;
// 我们需要存储部分结果 - 这就是使它复杂的原因
type StackEntry = {
node: TreeNode;
phase: "initial" | "left_done" | "right_done";
leftHeight?: number; // 存储左子树的结果
rightHeight?: number; // 存储右子树的结果
};
const stack: Array<StackEntry> = [{ node: root, phase: "initial" }];
let finalHeight = 0;
while (stack.length > 0) {
const entry = stack[stack.length - 1]; // 查看
if (entry.phase === "initial") {
// 第一次访问 - 探索左子节点
entry.phase = "left_done";
if (entry.node.left) {
stack.push({ node: entry.node.left, phase: "initial" });
} else {
entry.leftHeight = 0; // 没有左子节点 = 高度0
}
} else if (entry.phase === "left_done") {
// 左完成 - 捕获其结果并探索右
if (entry.node.left) {
// 从栈中弹出左子节点的结果
const leftResult = stack.pop();
if (leftResult != null) {
entry.leftHeight = finalHeight; // 保存左的计算高度
}
}
entry.phase = "right_done";
if (entry.node.right) {
stack.push({ node: entry.node.right, phase: "initial" });
} else {
entry.rightHeight = 0;
}
} else {
// 两个子节点都完成 - 计算此节点的高度
if (entry.node.right) {
stack.pop(); // 弹出右子节点
entry.rightHeight = finalHeight;
}
const leftH = entry.leftHeight ?? 0;
const rightH = entry.rightHeight ?? 0;
finalHeight = Math.max(leftH, rightH) + 1;
stack.pop(); // 弹出此节点
}
}
return finalHeight;
}要点: 是的,您可以将任何递归式DFS转换为迭代式。但看看复杂性的差异!
超越DFS: 转换为迭代的其他递归算法
为了证明这不是DFS特有的,这里有其他经典递归算法及其迭代等价物:
示例1: 快速排序(分治)
// 递归: 优雅的15行
function quicksortRecursive(arr: Array<number>, low: number, high: number) {
if (low >= high) return;
const pivot = partition(arr, low, high);
quicksortRecursive(arr, low, pivot - 1); // 排序左边
quicksortRecursive(arr, pivot + 1, high); // 排序右边
}
// 迭代: 需要显式栈来跟踪范围
function quicksortIterative(arr: Array<number>) {
const stack: Array<[number, number]> = [[0, arr.length - 1]];
while (stack.length > 0) {
const range = stack.pop();
if (range == null) continue;
const [low, high] = range;
if (low >= high) continue;
const pivot = partition(arr, low, high);
// 推入两个范围到栈(替换递归调用)
stack.push([low, pivot - 1]);
stack.push([pivot + 1, high]);
}
}示例2: 斐波那契(数学递归)
// 递归: 自然的数学定义
function fibRecursive(n: number): number {
if (n <= 1) return n;
return fibRecursive(n - 1) + fibRecursive(n - 2);
}
// 迭代: 自下而上方法(实际上更高效!)
function fibIterative(n: number): number {
if (n <= 1) return n;
let prev = 0;
let curr = 1;
for (let i = 2; i <= n; i++) {
const next = prev + curr;
prev = curr;
curr = next;
}
return curr;
}示例3: 回溯 - 生成所有排列
// 递归: 简洁的回溯模式
function permuteRecursive(nums: Array<number>): Array<Array<number>> {
const result: Array<Array<number>> = [];
function backtrack(current: Array<number>, remaining: Array<number>) {
if (remaining.length === 0) {
result.push([...current]);
return;
}
for (let i = 0; i < remaining.length; i++) {
backtrack(
[...current, remaining[i]],
[...remaining.slice(0, i), ...remaining.slice(i + 1)]
);
}
}
backtrack([], nums);
return result;
}
// 迭代: 复杂的状态管理
function permuteIterative(nums: Array<number>): Array<Array<number>> {
const result: Array<Array<number>> = [];
const stack: Array<{
current: Array<number>;
remaining: Array<number>;
}> = [{ current: [], remaining: nums }];
while (stack.length > 0) {
const state = stack.pop();
if (state == null) continue;
if (state.remaining.length === 0) {
result.push(state.current);
continue;
}
// 推入所有可能的下一个状态
for (let i = state.remaining.length - 1; i >= 0; i--) {
stack.push({
current: [...state.current, state.remaining[i]],
remaining: [
...state.remaining.slice(0, i),
...state.remaining.slice(i + 1),
],
});
}
}
return result;
}关键观察: 在每种情况下,您都可以将递归转换为迭代,但递归版本通常更清晰、更直观。迭代版本需要手动管理递归自动处理的状态。
应该何时使用每种?
等价性并不意味着迭代总是更好。这是实用的决策框架:
使用递归式DFS当:
- ✅ 自然适合 - 问题本质上是递归的(树操作、分治)
- ✅ 简单性很重要 - 更清晰、更容易理解和维护
- ✅ 无栈溢出风险 - 树深度合理(通常 < 1000层是安全的)
- ✅ 需要返回值 - 需要从子树收集和组合结果
- ✅ 标准遍历 - 递归最清晰的基本前/中/后序
示例: 递归在这里完美
// 在树中查找最大值 - 递归自然清晰
function findMax(node: TreeNode | null): number {
if (node == null) return -Infinity;
return Math.max(node.val, findMax(node.left), findMax(node.right));
}
// 迭代版本需要复杂的状态跟踪 - 不值得!使用迭代式DFS当:
- ✅ 栈溢出风险 - 非常深的树(数百万节点、数千层)
- ✅ 需要暂停/恢复 - 需要暂停并稍后恢复的长时间运行搜索
- ✅ 需要栈检查 - 必须查看当前路径或遍历状态
- ✅ 自定义控制流 - 需要回溯、跳过子树或在执行过程中修改遍历
- ✅ 内存约束 - 系统调用栈有限,但堆内存可用
示例: 迭代在这里必要
// 可暂停搜索 - 递归不可能
class PausableSearch {
private stack: Array<StackEntry>;
search(limit: number) {
while (this.stack.length > 0 && processed < limit) {
// 处理节点...
// 可以在这里暂停并稍后恢复!
}
}
}实际经验法则
除非有特定原因,否则对大多数算法默认使用递归:
- 95%的问题 → 使用递归(更简单、更清晰、更易维护)
- 5%有特殊需求 → 使用迭代(栈溢出风险、暂停/恢复、显式状态检查)
递归并不逊色 - 对大多数递归问题来说,它是自然的首选解决方案。迭代方法是当递归的限制成为实际问题时的强大工具,而不是您应该始终使用的"更好"方法。
为什么通常首选递归:
- 匹配问题结构 - 树遍历、分治和回溯本质上是递归概念
- 自文档化代码 - 递归代码通常读起来像数学定义或问题描述
- 不易出错 - 无需手动栈管理意味着更少的错误
- 编译器优化 - 现代编译器可以自动优化尾递归函数
当迭代变得必要时:
- 栈深度限制 - 系统调用栈通常限制为数千帧
- 外部约束 - 需要跨程序重启保存/恢复状态
- 性能关键 - 消除函数调用开销(尽管编译器经常这样做)
- 教育目的 - 理解递归在底层做什么
为什么有复杂性差异?
递归版本更简单是因为语言运行时处理状态管理:
- 调用栈自动保存局部变量
- 返回值自动向上流动
- 执行在正确的位置自动恢复
迭代版本必须手动实现所有这些:
- 在栈条目中显式保存变量
- 手动跟踪处于哪个处理阶段
- 编写代码来处理每个阶段转换
但如果迭代也清晰呢?
很好的问题: "如果递归的主要优势是清晰性,那么当迭代也清晰时,迭代不是更好吗?"
是的,绝对是! 当迭代解决方案同样清晰和直观时,它通常比递归更好,因为您获得:
- ✅ 无栈溢出风险
- ✅ 对执行的显式控制
- ✅ 更容易调试(可以直接检查栈)
- ✅ 更好的性能(无函数调用开销)
迭代自然更清晰的示例: 斐波那契
// 递归: 匹配数学定义但时间复杂度呈指数级
function fibRecursive(n: number): number {
if (n <= 1) return n;
return fibRecursive(n - 1) + fibRecursive(n - 2); // 重新计算相同的值!
}
// 迭代: 实际上更简单且更高效
function fibIterative(n: number): number {
if (n <= 1) return n;
let prev = 0,
curr = 1;
for (let i = 2; i <= n; i++) {
[prev, curr] = [curr, prev + curr]; // 简洁的单行更新
}
return curr;
}在这种情况下,迭代更优 - 它更简单、更易读且更高效。
迭代自然清晰的其他情况:
-
尾递归函数 - 这些只是伪装的循环:
// 尾递归: 最后一个操作是递归调用 function sumRecursive(n: number, acc: number = 0): number { if (n === 0) return acc; return sumRecursive(n - 1, acc + n); // 尾调用 } // 迭代同样清晰并避免栈帧 function sumIterative(n: number): number { let sum = 0; for (let i = 1; i <= n; i++) { sum += i; } return sum; } -
自下而上动态规划 - 迭代更自然:
// 从基本情况构建解决方案自然是迭代的 function climbStairs(n: number): number { if (n <= 2) return n; let prev = 1, curr = 2; for (let i = 3; i <= n; i++) { [prev, curr] = [curr, prev + curr]; } return curr; } -
简单线性遍历 - 循环比递归更清晰:
// 数组求和 - 迭代更自然 function sumArray(arr: Array<number>): number { let sum = 0; for (const num of arr) { sum += num; } return sum; }
关键原则: 对特定问题使用更清晰的方法。
大多数递归问题(树、分治、回溯)用递归更清晰,因为它们涉及:
- 多个递归调用
- 组合来自子树的返回值
- 自然的层次结构
但当迭代同样或更直观时(尾递归、线性遍历、自下而上DP),首选迭代以获得上述好处。
底线:
- 迭代能替代所有递归吗(不仅仅是DFS)? 是的,理论上任何递归算法都可以转换为迭代。
- 应该总是使用迭代而不是递归吗? 不,绝对不。
- 应该总是使用递归而不是迭代吗? 不,绝对不。
- 真正的规则: 对您的特定问题使用更清晰、更直观的方法。 实际上,这意味着对树/图/回溯使用递归(更清晰),对尾递归模式/线性遍历/自下而上DP使用迭代(同样或更清晰)。