本讲定位：编程题第 2 题的主战场。近三次真题的第 2 题全是树上 DFS：2026 年 6 月「满二叉树子树计数」、2026 年 3 月「完全二叉树子树计数」、2025 年 12 月「路径覆盖」。25 分，题型高度稳定。
六级第 03 讲已经在二叉树上把「后序汇总」这个模板建起来了。本讲做三件事：把 DFS 讲成一个通用方法（不局限于二叉树）、推广到一般树（孩子不止两个，输入是父亲数组）、把它用在带决策的问题上（树形 DP）。另外补上大纲里的网格 DFS 与回溯。
本讲建议安排两周。
对应官方大纲：六级知识块 3「搜索算法」——深度优先搜索算法（DFS）。
前置知识：六级第 02 讲（遍历）、六级第 03 讲（子树统计模板）、五级第 06 讲（递归、记忆化、剪枝）。
代码说明：本讲代码均已用 g++ 11.5（
-std=c++11）编译运行验证；两道真题程序在官方样例上输出一致，路径覆盖另与 $2^n$ 枚举暴力对拍。
$$ \boxed{\textbf{一条路走到底，走不动了就退回上一个岔路口，换一条继续}} $$
这就是「深度优先」：优先往深处走，而不是把身边的都先看一遍（那是下一讲的 BFS）。
前面其实一直在用它：
| 你写过的 | 其实就是 DFS |
|---|---|
| 二叉树的前/中/后序遍历（六级第 02 讲） | 在二叉树上的 DFS |
| 递归求高度、数叶子（第 02、03 讲） | DFS + 回来时汇总 |
| 满二叉树子树计数（六级第 03 讲） | DFS + 后序汇总 |
所以本讲不是从零开始，是给已经在用的东西起个名字、理清套路。
五级第 06 讲讲过：每次递归调用，系统在调用栈上压一层。DFS 的「退回上一个岔路口」，靠的正是弹栈。
也可以自己拿一个栈来写（六级第 02 讲第 3.4 节的非递归前序就是）：
| 写法 | 优点 | 缺点 |
|---|---|---|
| 递归 | 短、直观 | 深度太大会栈溢出 |
| 显式栈 | 不怕深 | 代码长，容易写错 |
⚠️ 判断题常客（2026 年 3 月六级单选第 13 题）：「对一棵树进行 DFS 时，常借助递归或栈实现」——正确。
同一题的三个错误选项也要会判：
- 「DFS 一定按层从上到下访问」——错，那是 BFS；
- 「对任意一棵树 DFS 得到的遍历序列唯一」——错，访问孩子的顺序不同，序列就不同；
- 「DFS 只能用于二叉树，不能用于普通树」——错，一般树同样能 DFS（本讲第 3 节）。
沿用五级第 06 讲的口径：
$$ \boxed{\text{递归深度} \le 10^5 \text{ 可以放心；} \ge 10^6 \text{ 必须改写成非递归}} $$
六级编程题的 $n$ 通常是 $10^5$，最坏情况（树退化成一条链）深度正好 $10^5$，能过。这一点要让学生安心，不要一看到 $10^5$ 就去写显式栈。