一、核心知识点清单
1. DFS基础概念
-
定义：深度优先搜索（Depth-First Search），一种“一条路走到底”的递归搜索算法。从初始点v出发，访问v，后选择与v相邻且未被访问的点w，以w为初始点，继续访问，递归进行。
-
类比：像走迷宫时，优先选择一条路走到死胡同，再回退到上一个岔路口（回溯），直到碰到一个未走过的岔路口、继续探索。
-
核心思想：递归 + 回溯。
2. DFS递归模板（Python版）
def dfs(当前状态):if 达到终止条件: # 例如找到了解、越界、访问过记录结果或处理逻辑returnfor 选择 in 所有可能的分支: # 遍历所有子节点或方向if 不满足条件: # 剪枝（跳过无效分支）continue标记当前状态（如visited[i] = True）dfs(下一状态) # 递归进入下一层撤销标记（回溯，如visited[i] = False）3. 术语
-
递归：函数调用自身，注意终止条件。
-
回溯：撤销上一步操作，恢复状态（关键易错点！）。
-
剪枝：提前跳过无效分支，提升效率。
4.举例说明
以这个图为例，从0开始，到1之后将1设为初始点，寻找未被遍历过且与之相邻的点3；这时将3设为初始点，继续寻找，此时的情况是，2和4均相邻且未被遍历，假设我们选择4进行下一步的初始点，访问之后已无相邻且未被遍历的点，即无满足条件的目标。此时回溯到上一初始点3，选择合适的目标2进行访问，访问完之后同样“ 到头”，继续回溯，一直都没有满足条件的目标，直到回溯到初始点0，此次搜索结束。
由此我们还可得出，dfs的搜索结果不唯一，此题中，01342和01324皆为答案。
5. 树的DFS遍历（最直观例子）
-
前序遍历：根 → 左 → 右
-
代码示例：
class TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightdef dfs(root):if not root:returnprint(root.val) # 处理当前节点dfs(root.left) # 递归左子树dfs(root.right) # 递归右子树
二、学习安排
第1个30分钟：理解概念
-
学习dfs基础知识点（例如网络视频和上述知识讲解），重点关注：
-
DFS的“深度优先”如何体现？
-
递归调用栈的执行顺序。
-
-
用纸笔画出二叉树的DFS遍历过程（如下图）：
1/ \2 3/ \ 4 5
预期输出：1 → 2 → 4 → 5 → 3
第2个30分钟：手写模板
-
抄写并背诵DFS模板。
-
修改模板实现二叉树的中序遍历（左→根→右）。
def inorder(root):if not root:returninorder(root.left)print(root.val)inorder(root.right)
第3个30分钟：基础题目实战
-
题目1：二叉树的所有路径（LeetCode 257）
-
要求：输出从根节点到所有叶子节点的路径。
-
关键点：用字符串记录路径，回溯时删除末尾节点。
-
代码框架：
def binaryTreePaths(root):def dfs(node, path):if not node.left and not node.right:res.append(path + str(node.val))returnif node.left:dfs(node.left, path + str(node.val) + "->")if node.right:dfs(node.right, path + str(node.val) + "->")res = []if root: dfs(root, "")return res
-
第4个30分钟：N皇后问题
洛谷题目
https://www.luogu.com.cn/problem/P1219
蓝桥n皇后题目
-
题目理解：在N×N的棋盘上放置N个皇后，使得它们互不攻击（即任意两个皇后不能在同一行、同一列或同一对角线上）。
-
简化版思路：
-
用一维数组
queens记录每行皇后的列号。 -
DFS逐行放置皇后，检查冲突时剪枝。
-
-
代码提示：
def solveNQueens(n):def dfs(row):nonlocal resif row == n: # 所有行已放满res = [['.' * i + 'Q' + '.' * (n - i - 1) for i in queens]]returnfor col in range(n):if all(col != queens[i] and row - i != abs(col - queens[i]) for i in range(row)):queens[row] = col # 放置皇后dfs(row + 1) # 进入下一行queens = [0] * n # queens[i]表示第i行皇后的列号res = []dfs(0)return res# 测试输出一种解 print(solveNQueens(4)) # 输出示例：[['.Q..', '...Q', 'Q...', '..Q.']]
关键点解释
-
剪枝条件：
-
col != queens[i]：检查列冲突 -
row - i != abs(col - queens[i])：检查对角线冲突
-
-
回溯：通过
queens[row] = col和递归后的隐式回溯（无需显式撤销，因为每次循环覆盖赋值）。
上面那个代码是输出一种解，即输出n皇后陈列放射最后的样态，如果要输出有几种摆法，还有下面一种算法。下面的代码对应的是蓝桥杯中n皇后的题目。
def NQueens(n):# 定义深度优先搜索函数，row 表示当前处理的行def dfs(row):# 当 row 等于 n 时，说明已经成功放置了 n 个皇后，方案数加 1if row == n:nonlocal countcount += 1return# 遍历当前行的每一列for col in range(n):# 检查当前列、主对角线和副对角线是否被占用if not (cols[col] or diag1[row + col] or diag2[row - col + n - 1]):# 若未被占用，标记当前列、主对角线和副对角线已被占用cols[col] = diag1[row + col] = diag2[row - col + n - 1] = True# 递归处理下一行dfs(row + 1)# 回溯操作，将当前列、主对角线和副对角线标记为未被占用cols[col] = diag1[row + col] = diag2[row - col + n - 1] = False# 初始化列标记数组，用于记录每一列是否被占用cols = [False] * n# 初始化主对角线标记数组，用于记录主对角线是否被占用diag1 = [False] * (2 * n - 1)# 初始化副对角线标记数组，用于记录副对角线是否被占用diag2 = [False] * (2 * n - 1)# 初始化方案数为 0count = 0# 从第 0 行开始进行深度优先搜索dfs(0)# 返回总的方案数return count# 读取用户输入的 n
N = int(input())
# 调用 NQueens 函数计算方案数并打印结果
print(NQueens(N))来详细分析一下这个代码，定义一个总函数，总函数中包含dfs函数和初始化标记。
1、主函数NQueens是一个接受一个整数参数 n 的函数，n 代表棋盘的大小（即 n×n 的棋盘），函数的目的是返回在这个棋盘上放置 n 个皇后的所有可行方案的数量。
2、初始化标记
cols = [False] * ndiag1 = [False] * (2 * n - 1)diag2 = [False] * (2 * n - 1)count = 0cols是一个长度为n的布尔型列表，用于标记每一列是否已经被皇后占据。初始时，所有列都未被占据，所以列表中的元素都为False。diag1是一个长度为2 * n - 1的布尔型列表，用于标记从左上到右下的主对角线是否被皇后占据。因为在n×n的棋盘上，主对角线的数量为2 * n - 1条，所以列表长度为2 * n - 1。初始时，所有主对角线都未被占据，元素都为False。diag2是一个长度为2 * n - 1的布尔型列表，用于标记从右上到左下的副对角线是否被皇后占据。同样，副对角线的数量也是2 * n - 1条，初始时所有副对角线都未被占据，元素都为False。count是一个整数变量，用于记录所有可行的放置方案的数量，初始值为 0。
这里解答一个疑问，对角线列表的元素为什么为2*n-1。这里的对角线其实指的就是每个以45度角平分正方形的每条线。不难得出，这么去切的时候，2*2的矩阵有三条线（分别是分割对角两个小正方形和分隔大正方形的最大对角线），以此类推便很容易理解。
3、深度优先搜索函数 dfs
def dfs(row):if row == n:nonlocal countcount += 1return参数 row 为当前正在处理的行号。当 row 等于 n 时，意味着已经成功地在每一行都放置了一个皇后，找到了一种可行的放置方案。此时，使用 nonlocal 关键字引用并修改外层函数的 count 变量，将其加 1，表示找到了一种新的方案，然后返回。
4、寻找n皇后的放置位置
for col in range(n):if not (cols[col] or diag1[row + col] or diag2[row - col + n - 1]):cols[col] = diag1[row + col] = diag2[row - col + n - 1] = Truedfs(row + 1)cols[col] = diag1[row + col] = diag2[row - col + n - 1] = False-
对于当前行
row，遍历每一列col。 -
cols[col]用于检查第col列是否已经被占据；diag1[row + col]用于检查当前位置所在的主对角线是否已经被占据；diag2[row - col + n - 1]用于检查当前位置所在的副对角线是否已经被占据。如果这三个条件都不满足，说明当前位置可以放置皇后。（这里如何表达对角线上的位置需要格外注意） -
如果当前位置可以放置皇后，将
cols[col]、diag1[row + col]和diag2[row - col + n - 1]都标记为True，表示该列和对应的对角线已经被占据。 -
递归调用
dfs(row + 1)，继续处理下一行。 -
回溯操作：当递归返回时，将
cols[col]、diag1[row + col]和diag2[row - col + n - 1]都标记为False，表示撤销当前位置的皇后放置，以便尝试其他可能的放置方案。（不回溯就没有办法继续寻找其他方案）
5、调用dfs
dfs(0)return count-
从第 0 行开始调用
dfs函数进行深度优先搜索。 -
最后返回
count，即所有可行的放置方案的数量。
四、常见错误提醒
-
忘记回溯：例如八皇后问题中修改
queens后没恢复状态。 -
递归终止条件错误：导致无限递归（如二叉树遍历忘记判断
if not root）。 -
剪枝不彻底：在排列问题中未去重，导致重复解。
五、自查清单
-
能独立写出DFS模板？
-
能解释八皇后问题的剪枝逻辑？--即什么情况下跳过分支（三个冲突）
-
能手动模拟二叉树DFS的递归栈？
