LeetCode刷到第44天，我终于决定把DFS这块硬骨头正经啃一啃。说实话，前面几周做题时没少遇见“这题用DFS就完事了”的题解，但基本都是看懂了就划走，真正轮到自己上手写，反而会在递归入口和状态回溯这种地方反复犯迷糊。如果你也处于“听说过DFS、能读懂别人的递归、轮到自己写就卡壳”的阶段，那今天这篇笔记应该能帮你把整条线捋清楚。
DFS，全称深度优先搜索（Depth-First Search），是计算机算法里最基础、最绕不开的搜索方式。它要解决的核心问题可以用一句话概括：在一个状态空间里，找到满足条件的路径，或者穷举出所有可行方案。数独求解、迷宫寻路、全排列生成、树的遍历、图的连通性判断，底层骨架全是DFS。这篇内容适合正在刷题准备面试的开发者，也适合刚学完数据结构与算法的初学者，我会从原理讲到模板，再把我自己踩过的坑和排查经验都交代清楚，建议配合IDE边看边敲。
1. 为什么说DFS是所有搜索算法的地基
很多人对DFS的第一印象是“不就是递归吗”，这个直觉没错，但只对了一半。递归是实现DFS最顺手的方式，DFS却是比递归更底层的搜索思想。理解这层关系，后面写回溯、写剪枝、写记忆化搜索都会顺很多。
1.1 DFS到底在干什么：把“一条道走到黑”变成可复用的策略
我经常用一个生活例子来解释DFS的工作方式：想象你在一个陌生的地下迷宫里找出口，手里没有地图。你的策略是随便挑一条路一直往前走，遇到岔路就选一条继续走，直到死胡同为止。走到死胡同之后，你退回到最近的一个岔路口，再选另一条没走过的路试。这个“遇到死路就往回退，退回岔路再换方向”的过程，就是深度优先搜索。
它和广度优先搜索（BFS）的区别也在于此：BFS更像是往水池里扔一块石头，波纹一圈一圈向外扩散，逐层推进；DFS则更像一个执着的探险家，非要走到尽头才肯回头。两种策略各有优劣，但DFS最大的优势是代码简洁、状态容易携带——你只需要维护一条从起点到当前节点的路径，而不用像BFS那样维护一整层的节点集合。
在算法题里，DFS最常见的三种用途是：遍历（把所有节点走一遍）、搜索（找到满足条件的解）、穷举回溯（枚举所有可能的组合）。这三种用途本质上都建立在同一个状态转移模型上：从一个状态出发，依次尝试所有可能的决策，每走一步就进入下一个状态，直到不能再走或满足终止条件。
1.2 递归与栈：系统在幕后帮你维护的“后悔栈”
递归为什么天然适配DFS？因为函数调用本身就是栈结构。每次调用dfs()，系统会把当前函数的局部变量、返回地址压入调用栈；函数返回时，系统自动把这些状态弹出。这个机制恰好对应了DFS里的“前进”和“回溯”——前进时压栈，回溯时弹栈，你甚至不需要自己写代码去保存“上一次走到哪了”，系统全帮你记着。
举个最简单的例子，遍历一颗二叉树：
def dfs(node): if node is None: return # 访问当前节点，比如打印它的值 print(node.val) dfs(node.left) dfs(node.right)执行流程是这样的：先访问根节点，然后一头扎进左子树；左子树走完了，函数一层层回退，回到根节点这一层后，再进入右子树。你在纸上画一下函数调用栈的变化，会发现栈的深度正好等于当前递归链的长度。
当然，递归有递归的问题：递归深度过大时容易爆栈，而且系统调用栈会引入额外的函数调用开销。所以某些时候我们会手动用一个栈来模拟递归，这叫“显示栈DFS”。不过对于入门选手，我强烈建议先把递归写法练到条件反射，再去折腾迭代写法，因为递归写法更贴近DFS的逻辑本质，还更容易和后面的回溯模板无缝衔接。
2. DFS序的套路：把一棵树“拉直”成一维区间
很多人在DFS专题里都会碰到一个说法：dfs序模板题。这其实是DFS非常经典的一类应用，它不是在树上搜索一个目标，而是利用DFS的访问顺序，把一棵树“拍平”成一个一维序列，从而把很多树上操作变成区间操作。
2.1 进时间戳和出时间戳：每个节点都拥有一段连续区间
对一棵树从根节点进行DFS，用一个全局递增计数器stamp记录访问顺序。当第一次访问到节点u时，记录dfn_in[u] = ++stamp；当u的所有子树都遍历完、即将离开u时，记录dfn_out[u] = stamp。
这里有一个特别重要的性质：任意节点u的整棵子树，包含的所有节点在dfn_in上是一段连续的区间，区间范围就是[dfn_in[u], dfn_out[u]]。
为什么？因为DFS是深度优先的，它进入节点u之后，会一直递归处理u的所有子树，在递归过程中访问到的每一个节点都是u的子孙节点。在这个过程结束之前，DFS不会回头去访问u的兄弟节点或父节点的其他分支。所以u子树里的所有节点在访问顺序上必然紧紧挨在一起，形成一段连续区间。
反过来也可以利用这个性质判断祖先关系：节点v是u的子孙，当且仅当dfn_in[u] <= dfn_in[v] <= dfn_out[u]。这是一个O(1)的祖先判断，比从v一步步往上爬快得多。
2.2 子树区间化之后的经典应用
区间一旦形成，树上的子树操作就能套用区间数据结构的现成方法。举几个典型的例子：
- 子树求和：给出一棵树，多次询问以
u为根的子树中所有节点的权值和。先DFS预处理，得到每个节点对应的区间[dfn_in[u], dfn_out[u]]，再把每个节点的权值放到它的dfn_in位置上，于是问题变成“求数组区间[L, R]的和”，用前缀和或者树状数组就能轻松应付。 - 子树节点全部加上一个数：同样的思路，变成“区间加、区间查询”，交给线段树或者差分数组处理。
- 判断两点之间是否有祖先后代关系：上面说的区间包含判断，常用于LCA（最近公共祖先）相关算法的预计算阶段。
我第一次理解这个套路时，有种“原来如此”的爽感——树的深度结构，硬是被DFS转换成了线性的时间序列，空间复杂度O(n)就搞定。面试中考“DFS序遍历”的题目并不罕见，尤其是树链剖分、在线LCA这类进阶问题，DFS序几乎是第一步。
3. 三套DFS模板代码，背熟就能应对大多数题目
模板这东西，光看不练是没用的，但背也要有选择地背。我把平时用得最多的三套DFS框架整理一下，每套都对应一类高频题型。建议你在理解的基础上把它们敲成肌肉记忆，尤其是第二套回溯模板，面试手写题里出现概率非常高。
3.1 图遍历框架：最基础的状态标记写法
图的DFS最需要注意的是visited数组。无向图或有向图都可能出现环，如果不做访问标记，递归就会在环里无限打转。
visited = [False] * n def dfs(u): visited[u] = True for v in graph[u]: if not visited[v]: dfs(v) # 调用方式：对每个未访问的节点调用 dfs(i)这里有个细节值得注意：visited[u] = True这一行放在进入dfs(u)时执行，而不是在遍历邻居时才执行。原因很简单——一旦节点u被加入当前搜索的路径，它就应当被立刻标记，否则在递归的某个更深层次，可能会出现两条不同的路径同时认为“自己可以访问u”，造成重复访问甚至死循环。
树的遍历则是这个框架的特例，因为树本身无环，所以可以省掉visited，改成在递归时不走父节点即可：
def dfs_tree(u, parent): for v in tree[u]: if v == parent: continue dfs_tree(v, u)3.2 回溯框架：穷举所有方案的标准姿势
回溯问题是DFS的重头戏。全排列、组合总和、子集分割、N皇后，全都长一个样。核心就是三件事：做选择、递归、撤销选择。
ans = [] path = [] def backtrack(选择列表): if 满足终止条件: ans.append(path[:]) # 注意一定要拷贝一份 return for 选择 in 选择列表: if 选择不合法: continue # 1. 做选择 path.append(选择) 更新状态(标记已使用) # 2. 进入下一层决策 backtrack(新的选择列表) # 3. 撤销选择 path.pop() 还原状态(取消标记)写这个模板最容易翻车的地方，就是最后一步“撤销选择”。因为递归返回之后，当前层的状态必须恢复成进入之前的样子，否则下一轮for循环看到的会是污染过的状态。我见过不少新手在这里漏掉path.pop()，结果一份答案里莫名其妙混进了上一次搜索的残留节点。另外注意ans.append(path[:])而不是ans.append(path)，后者存的是同一个列表的引用，回溯之后所有答案会互相覆盖，最终得到一堆相同的空列表。这个坑我在第5章还会细讲。
3.3 树的DFS序遍历模板：拍平树结构的关键代码
无论后续用树状数组还是线段树，DFS序的预处理代码其实都是一样的：
dfn_in = [0] * (n + 1) dfn_out = [0] * (n + 1) stamp = 0 def dfs_stamp(u, parent): global stamp stamp += 1 dfn_in[u] = stamp for v in tree[u]: if v == parent: continue dfs_stamp(v, u) dfn_out[u] = stamp注意stamp的递增是在进入节点时做的，dfn_out是在所有孩子处理完之后才记录。这样dfn_out[u]记录的其实是u子树里最后一个被访问到的节点的时间戳，而不是“u离开”的新时间戳。这也是为什么dfn_out用的不是++stamp而是直接赋值stamp——因为不需要再创造一个新的时间戳。
4. 剪枝：从超时到AC之间最大的那道坎
裸DFS的问题非常明显：状态数量经常是爆炸性的。求n个元素的全排列是O(n!)，枚举子集是O(2^n)，棋盘类问题更是动辄指数级。如果不加任何优化，一个稍微大一点的测试点就能让程序跑到天荒地老。这时候，剪枝就决定了你的代码是AC还是TLE。
4.1 可行性剪枝和最优性剪枝：最常用的两把剪刀
可行性剪枝的思路是：当前分支已经可以判定不可能产生合法解了，直接不再递归。比如N皇后问题中，如果在第i行放置皇后时，这个位置和前面已经放置的皇后处于同一列或同一对角线，那么这个分支肯定无法构成合法解，直接continue，不用再往下试了。
最优性剪枝更常见于最优化问题：当前已经得到的部分解，它的代价已经不比全局最优解更好了，那么继续向下搜索也不可能超越当前最优解，直接截断。比如最小步数问题里，走到当前节点已经用了step步，而全局答案是best，如果step >= best，继续往下只会让步数更大，剪掉即可。
我给你一个很直观的例子，走迷宫求最短步数：
best = float('inf') def dfs(x, y, step): global best if x == tx and y == ty: best = min(best, step) return if step >= best: # 最优性剪枝 return for dx, dy in directions: nx, ny = x + dx, y + dy if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny]: visited[nx][ny] = True dfs(nx, ny, step + 1) visited[nx][ny] = False这里if step >= best就是典型的最优性剪枝。它的作用在于：一旦发现当前路线的步数已经超过我们之前找到过的最短路径，这条路再走下去没有意义，立刻回头。
4.2 奇偶性剪枝、排序预处理和记忆化搜索：进阶优化技巧
除了上面两种通用的剪枝，还有一些针对特定场景的进阶套路。
奇偶性剪枝常见于迷宫逃出类问题。假设当前在(x, y)，终点是(tx, ty)，剩余可用步数是rem。从起点到终点的曼哈顿距离dist = abs(tx - x) + abs(ty - y)。如果dist和rem的奇偶性不一致，那么无论怎么绕，都不可能恰好用rem步到达终点。因为每一步都会改变横纵坐标之和的奇偶性，步数的奇偶性和最终位置坐标的奇偶性之间存在固定约束。这个判断能在搜索入口就排除掉一大批不可能到达的分支。
排序预处理主要是改变遍历for循环的顺序。例如在组合总和问题中，先把候选数组从小到大排序，然后在DFS中一旦当前元素加上已经选的值超过了目标值，后面更大的元素也不需要再试，直接break。这种做法不仅能利用大小关系提前终止遍历，还能让更可能产生最优解的大数值先被考虑，从而更快更新best，增强最优性剪枝的效果。
记忆化搜索则是另一条路线：把已经搜索过的状态结果保存起来，下次遇到相同状态直接返回，避免重复计算。本质上它已经是动态规划（DP）的雏形了，只是用DFS的自顶向下方式实现。很多题解里说的“记忆化”，可以理解成“带缓存的DFS”，解决的问题是递归展开时大量重复子问题。比如计算斐波那契数列，朴素DFS是指数复杂度，加上一个memo字典后就变成了O(n)。
memo = {} def fib(n): if n <= 1: return n if n in memo: return memo[n] memo[n] = fib(n - 1) + fib(n - 2) return memo[n]我把记忆化搜索单独拎出来说，是因为它经常被初学者忽略：明明DFS写出了一版正确的递归，却因为重复计算太多而卡成TLE，加上memo之后瞬间AC，这种对比非常感人。
5. 那些让你debug到凌晨的DFS常见坑
最后这部分是我最想分享的实战经验。DFS代码本身不长，但出起bug来非常恶心——因为递归调用链条长、层次多，一旦状态被污染，问题往往隐藏得很深，不容易一眼看出来。下面几个坑我全都亲手踩过。
5.1 死循环与错误访问：visited标记的位置不对
先说一个细节问题。有些人在遍历图时会这样写：
def dfs(u): for v in graph[u]: if not visited[v]: visited[v] = True # 在扩展邻居时才标记 dfs(v)这个写法有一个隐蔽的漏洞：当多个邻居都能访问到同一个未标记节点时，该节点可能被重复加入递归。更关键的是，visited[u]本身没有被提前标记，在递归入口进入u时，如果有另一条路径也能到达u，u会被再次递归。正确做法是进入dfs(u)时立刻标记：
def dfs(u): visited[u] = True for v in graph[u]: if not visited[v]: dfs(v)这一个细节的差别，就是死循环和正确代码之间的距离。回想一下我第3章图遍历模板的写法，就是特意把这个点放在第一行的。
5.2 递归爆栈与Python递归深度限制
DFS是递归的“重灾区”。一条链状树的深度可能达到10万甚至百万，这时C++默认的栈空间（通常8MB左右）都可能爆掉；Python更夸张，默认递归深度上限只有1000，超过就抛RecursionError。
如果你在LeetCode上跑数据很大的树形题，突然报RecursionError: maximum recursion depth exceeded，多半就是这个问题。我们可以用sys.setrecursionlimit把限制调大：
import sys sys.setrecursionlimit(1 << 20) # 大约100万但注意这只是把Python层面的限制调大，底层栈空间耗尽时依然会段错误。数据规模极端大时，最稳妥的方案是改成显式栈，自己用list模拟递归过程。这种做法虽然写起来更啰嗦，但可控性高，不会受调用栈容量制约。
5.3 回溯不干净与列表引用陷阱
我在第3章强调过：收集答案时要ans.append(path[:])，而不是ans.append(path)。为什么？因为path是全局唯一的列表对象，回溯过程中不断append和pop，每一轮循环结束后，path的内容都在变化。如果直接存path引用，最终ans里的所有元素都会指向同一个列表，而这个列表最后被弹空了，结果就是ans里面全是空列表。
同样的问题也出现在嵌套函数的可变参数上。比如用path作为参数传入递归函数，在函数内部修改它，再把它存入答案时，依然需要拷贝。
关于调试，有一个特别实用的土办法：
def dfs(depth, u): print(" " * depth + f"enter: u={u}") ... print(" " * depth + f"leave: u={u}")在递归进出的位置打印缩进日志，能够非常直观地看到DFS的调用树长什么样，也能很快定位到哪个分支的回溯没有正确恢复状态。我每次递归逻辑理不清时，就会加上这种日志跑一遍小数据，很多时候问题瞬间浮出水面。
我个人做DFS相关题目的体会是：模板本身并不难，难的永远是“状态边界”和“优化时机”。很多题靠的不是灵感，而是把基础模板和对状态空间的敏感度揉在一起——先画出递归树，再想清楚每个节点之间怎么转移、哪些分支可以砍掉。这个过程熟练之后，解大部分搜索题都会有种“条件反射”的手感。上面讲的DFS序、回溯、剪枝和记忆化，看起来是四个方向，其实骨子里是同一套思维，建议你在刷题时把它们相互串联着练，效果比孤立地背模板好得多。
