搜索、回溯与树算法

这篇来自我补“搜索、回溯与树算法”基础时的一次复盘。我之前的问题是：我早期写 DFS、回溯和树遍历时觉得它们长得都差不多，也因此经常把访问标记、撤销选择和返回值混在一起。等我把输入、状态变化和边界条件分别写出来之后，原来看似突然出现的规则就有了来路。

搜索、回溯与树算法这一章负责训练“状态空间”的感觉。很多题目表面是数组、字符串、棋盘、树，底层其实都是状态节点之间的移动。

这一章最重要的能力是：能把问题画成一棵树或一张图，然后知道什么时候深搜，什么时候广搜，什么时候剪枝，什么时候用树上的递归状态合并。

先把问题画成岔路

走迷宫时，每个位置是一个状态，每次上下左右移动产生下一批状态。要找任意出口，可以沿一条路走到底再回退；要找最少步数，则应从起点一层层向外扩展。排列组合题也是一样，只不过岔路变成“这一位选择哪个元素”。

这一章的共同语言只有四个词：状态、选择、访问记录、终止条件。先能在纸上画出前两三层，再写递归或队列代码。

我为什么先补这一章

这一章重点解决：

1. DFS、BFS、拓扑排序分别适合什么问题。
2. 回溯为什么需要选择、进入、撤销。
3. 树的遍历如何连接路径、深度、直径、LCA。
4. 如何避免搜索时重复访问和无效分支。

我自己的学习顺序

1. 搜索算法：DFS、BFS 与拓扑排序。
2. 回溯算法：从状态树到剪枝。
3. 树算法：从遍历到最近公共祖先。

我当时最容易混淆的地方

DFS 更适合走到底、枚举路径、判断连通；BFS 更适合最短步数、层级扩散；拓扑排序适合依赖关系。

回溯不是普通递归，它强调“选择现场”的恢复。进入下一层之前做选择，返回上一层之前撤销选择。

树算法的很多问题都可以拆成“当前节点要什么信息、子节点返回什么信息、当前节点如何合并”。

我后来这样检查自己是否真的理解

• 为什么 BFS 能求无权图最短路径？
• 回溯为什么通常需要剪枝？
• 树的后序遍历为什么适合计算子树信息？
• 拓扑排序失败意味着什么？