只会递归DFS远远不够！

前言

前端面试中，算法题越来越卷。DFS（深度优先搜索）作为树/图遍历的基石，几乎逢面必考。但很多人停留在"会写递归版 DFS 就行"的阶段，一遇到爆栈——就懵了。

本文从 DFS 的核心思想出发，逐层递进到迭代，把理论和实战串成一条线。

一、DFS 到底是什么？

一句话：沿着一条分支一路走到底，撞了南墙再回头探索另一条分支。

用下面这棵树举例：

A
/ \\
B C
/ \\ \\
D E F

先序遍历（根 → 左 → 右）的访问顺序是：A → B → D → E → C → F

你看，A 出发一路往左下探到 D（到底了），回溯到 B 再探 E（到底了），再回溯到 A 探 C，最后到底 F。这就是 DFS 的核心节奏——纵深优先，不撞南墙不回头。

DFS vs BFS 一张表对比

二、递归实现：DFS 最自然的写法

递归和 DFS 是天生一对——函数的层层调用本身就是栈。

function dfs(root, res = []) {
if (!root) {
return; // 退出条件：走到叶子节点下面了
}
res.push(root.val); // 处理当前节点（先序）
dfs(root.left, res); // 递归左子树
dfs(root.right, res); // 递归右子树
return res; // 返回结果
}

这段代码只有 8 行，但信息量不小：

递归版简洁优雅，缺点是深度过大时可能爆栈（Stack Overflow）。

三、迭代实现：手动用栈模拟递归

搞懂迭代版 DFS 是面试的分水岭——面试官想看你是否真的理解"栈"这个核心。

function dfsPreOrderInter(root) {
if (!root) {
return;
}
const stack = [root]; // 手动维护一个栈
const res = [];
while (stack.length) {
const node = stack.pop(); // 弹出栈顶，处理当前节点
res.push(node.val);
// 注意：先 push right 再 push left，因为栈是后进先出
if (node.right) {
stack.push(node.right);
}
if (node.left) {
stack.push(node.left);
}
}
return res;
}

关键点来了：为什么先 push 右子节点？

因为栈是 LIFO（后进先出）。我们希望先访问左子节点，所以左子节点必须后入栈，这样它才会先被 pop 出来。这个细节搞反了整棵树的遍历顺序就反了，面试现场翻车的十有八九栽在这里。

把递归版和迭代版放一起看，核心逻辑完全一致：