遍历视角：回溯与 DFS

回溯与 DFS 到底差在哪

一句话版本

回溯的操作在「树枝」上，DFS 的操作在「节点」上。

对着代码看就很直白：

// 回溯：操作在 for 循环内部，包着递归调用
function backtrack(node) {
  for (const child of node.children) {
    做选择;                 // ← 在「走向 child 这根树枝」上
    backtrack(child);
    撤销选择;               // ← 同一根树枝
  }
}
// DFS：操作在 for 循环外部，包着整个循环
function dfs(node) {
  做选择;                   // ← 在「node 这个节点」上
  for (const child of node.children) {
    dfs(child);
  }
  撤销选择;                 // ← 同一个节点
}

⭐ 两段代码只差一件事：那两行在 for 里面还是外面。 但它决定了你的操作对象是边还是点——很多题里这个区别是致命的。

为什么这个区别是致命的

举个最小的例子：给二叉树每个节点的值加一。

DFS 做得到，因为它的操作发生在节点上：

function plusOne(root) {
  if (root === null) return;
  root.val++;              // 就在这个节点上
  plusOne(root.left);
  plusOne(root.right);
}

回溯的写法做不到。回溯的操作位置在 for 里面，它能表达的是 「走这条边的时候干什么」，而根节点不在任何一条边的末端—— 它永远不会被访问到。

⚠️ 反过来也一样。回溯题里「撤销选择」必须精确对应「做选择」的那根树枝， 挪到 for 外面就变成了「进这个节点时做一次、出这个节点时撤一次」， 兄弟分支之间的隔离就没了。

📌 判据：关心「经过了哪些点」用 DFS，关心「走了哪些边、路径长什么样」用回溯。

遍历顺序完全一样

容易误会的一点：这两者的遍历顺序是一模一样的，都是深度优先。 它们走的是同一棵树、同样的路线，区别只在于「在旅途的哪一刻记账」。

所以不存在「DFS 比回溯快」这种说法。复杂度都是节点数 × 每节点耗时。

为什么名字这么混乱

网上常见「回溯就是 DFS」「回溯是 DFS 的一种」这类说法，都不算错， 因为这两个词本来就来自不同的语境：

  • DFS 是一种遍历策略，跟 BFS 相对。它描述的是“先深后广”这个走法。
  • 回溯 是一种解题方法，跟贪心、动规相对。它描述的是“试错 + 撤销”这个思路。

一个说怎么走，一个说走的时候干什么，本来就不在一个维度上。 回溯用的确实是 DFS 的走法，所以「回溯是一种 DFS」成立； 但反过来 DFS 不一定回溯（岛屿题就不撤销）。

⭐ 面试被问到时，答「它们遍历顺序相同，区别在于操作是写在 for 循环内还是外， 也就是作用在边上还是点上」，比背定义有说服力得多。

那「撤销」到底什么时候需要

这才是实践中真正要判断的。判据是：

你维护的状态，是否需要在离开这个分支后还原？

场景 撤销 为什么
排列/组合的 track 路径 需要 兄弟分支不能看见彼此的选择
网格 DFS 的「淹没」 不需要 淹掉就是永久的，正是我们要的
求所有根到叶的路径 需要 同第一行
图的连通分量计数 不需要 访问过就不该再访问
判断图中是否存在环 需要（部分） 见下

🚨 最后一行是唯一需要小心的：有向图找环要维护两个集合，撤销规则相反。

function hasCycle(graph, n) {
  const visited = new Set();   // 这辈子访问过 —— 不撤销
  const onPath  = new Set();   // 在当前这条路径上 —— 必须撤销
  let found = false;

  function dfs(u) {
    if (onPath.has(u)) { found = true; return; }   // 撞上自己走过的路 = 有环
    if (visited.has(u)) return;                    // 之前查过，不用再查

    visited.add(u);
    onPath.add(u);
    for (const v of graph[u]) dfs(v);
    onPath.delete(u);                              // 只删这一个
  }

  for (let i = 0; i < n; i++) dfs(i);
  return found;
}

两种错法的症状完全不同，值得分开记：

onPath 忘了撤销 —— 把「访问过」和「在路径上」混为一谈，于是误报。 一张 0→1, 0→2, 1→3, 2→3 的菱形 DAG（无环）会被判成有环。

⭐ 机制说准一点：忘撤销之后 onPath 变成了 visited 的同义词， 于是任何「被两条不同路径到达的节点」都会误报。菱形里节点 3 正是这样 —— 沿 0→1→3 进去一次、沿 0→2→3 又进去一次，第二次撞上 onPath 里还留着的自己。 （实测该节点一共被进入 3 次：外层那个 for (let i = 0; i < n; i++) dfs(i) 轮到 i = 3 时还会再调一次 —— 注意 onPath 的检查写在 visited 之前， 所以那一次也照样误报。）

visited 也跟着撤销 —— 结果仍然正确，但退化成枚举所有路径。 拿一张 15 个节点、每层两条平行边的分层 DAG（共 2¹⁴ = 16384 条路径）实测：

visited 不撤销（正确）:     43 次递归调用
visited 也撤销（错误）:  65519 次递归调用     ← 1524 倍
两者结论都是 false

⭐ 这两个数都能推出来，不用只当实测值记（N = 15）：

不撤销  1 + 2(N−1) + (N−1) = 43
        ↑起点  ↑每个节点被两条平行边各进一次（第二次立刻返回）
                      ↑外层 for 对已访问的 N−1 个节点各调一次
也撤销  Σ_{k=1}^{N} (2^k − 1) = 2^(N+1) − 2 − N = 65519
        ↑外层从第 i 个节点出发时，整棵 2 分叉的递归树都会重新展开一遍

📌 顺带解释了那个看着很怪的 65519 —— 它是 2¹⁶ − 17，不是随手量出来的。

⚠️ 答案是对的，所以对拍、跑样例都发现不了 （2 万组随机有向图对拍，两者结论零差异），只有数据量上去才超时。 判据不是「结果对不对」，而是问自己： 这个标记描述的是「历史」还是「当前路径」？ 历史不撤，路径必撤。

小结

回溯 DFS
操作位置 for 循环内 for 循环外
作用对象 树枝（边） 节点（点）
典型题 排列、组合、子集、N 皇后 岛屿、连通分量、区域填充
通常撤销 是 否
遍历顺序 深度优先 深度优先（相同）

往后看

这一章讲的都是遍历视角——关注路径、关注过程。

另一条路是子问题视角： 让递归函数返回值，用子问题的答案拼出原问题的答案。 它往下走就是分治与动态规划， 也是下一章的内容。

练习

勾选记录做过哪些，0 / 4 道。进度只存在这台设备的浏览器里；同一道题在别篇勾过，这里也会显示已做。

⚖️ 这里只给题号、官方标题和链接，不复述题面 —— 平台的题面文字有版权。 「这题考什么」写的是它对应本篇的哪个点，那部分是本站自己的内容。