搜索

搜索题目本质就是将题目中的状态映射为图中的点，将状态间的联系映射为图中的边。根据题目信息构建状态空间，然后对状态空间进行遍历，遍历过程需要记录和维护状态，并通过剪枝和数据结构等提高搜索效率。

状态空间

状态空间其实就是一个图结构，图中的节点表示状态，图中的边表示状态之前的联系，这种联系就是题目给出的各种关系。

DFS 和 BFS

DFS 和 BFS 是搜索的核心，贯穿搜索篇的始终，因此有必要先对其进行讲解。

DFS

题目的状态空间映射到一张图，状态就是图中的节点，状态之间的联系就是图中的边，那么 DFS 就是在这种图上进行深度优先的遍历。而 BFS 也是类似，只不过遍历的策略变为了广度优先，一层层铺开而已。

常见的DFS用来解决什么问题？(1) 图中（有向无向皆可）的符合某种特征（比如最长）的路径以及长度（2）排列组合（3）遍历一个图（或者树）（4）找出图或者树中符合题目要求的全部方案
DFS基本模板（需要记录路径，不需要返回值 and 不需要记录路径，但需要记录某些特征的返回值）
除了遍历之外多数情况下时间复杂度是指数级别，一般是O(方案数×找到每个方案的时间复杂度)
递归题目都可以用非递归迭代的方法写，但一般实现起来非常麻烦

算法模板

网格结构要比二叉树结构稍微复杂一些，它其实是一种简化版的图结构。要写好网格上的 DFS 遍历，我们首先要理解二叉树上的 DFS 遍历方法，再类比写出网格结构上的 DFS 遍历。我们写的二叉树 DFS 遍历一般是这样的：

void traverse(TreeNode root) {
    if(root == null) {
        return;    
    }
    // 访问两个相邻结点：左子结点、右子节点
    traverse(root.left);
    traverse(root.right);
}

网格DFS遍历的框架，下面我们借助递归来完成 DFS。

boolean[] visited = new boolean[n];

private void dfs(int i) {
    if (满足特定条件) {
        // 返回结果 or 退出搜索空间
    }
    visited[i] = true;
    for (根据 i 能到达的下一个状态 j) {
        if (!visited[j]) { // 如果状态 j 没有被搜索过
            dfs(j);
        }
    }
}

例题

543. 二叉树的直径 (简单) （分治）

124. 二叉树中的最大路径和 (困难)（分治）

226. 翻转二叉树 (简单)（分治）

101. 翻转二叉树 (简单)（分治）

951. 翻转等价二叉树 (中等)（分治）

236. 二叉树的最近公共祖先 (中等)（回溯 or 分治）

105. 从前序与中序遍历序列构造二叉树 (中等)（分治）

104. 二叉树的最大深度 (简单)（回溯 or 分治）

BFS

BFS BFS 也是图论中算法的一种。不同于 DFS， BFS 采用横向搜索的方式，从初始状态一层层展开直到目标状态，在数据结构上通常采用队列结构。

具体地，我们不断从队头取出状态，然后将此状态对应的决策产生的所有新的状态推入队尾，重复以上过程直至队列为空即可。

注意这里有两个关键点：

将此状态对应的决策。实际上这句话指的就是状态空间中的图的边，而不管是 DFS 和 BFS 边都是确定的。也就是说不管是 DFS 还是 BFS 这个决策都是一样的。不同的是什么？不同的是进行决策的方向不同。
所有新的状态推入队尾。上面说 BFS 和 DFS 是进行决策的方向不同。这就可以通过这个动作体现出来。由于直接将所有状态空间中的当前点的邻边放到队尾。由队列的先进先出的特性，当前点的邻边访问完成之前是不会继续向外扩展的。这一点大家可以和 DFS 进行对比。

最简单的 BFS 每次扩展新的状态就增加一步，通过这样一步步逼近答案。其实也就等价于在一个权值为 1 的图上进行 BFS。由于队列的单调性和二值性，当第一次取出目标状态时就是最少的步数。基于这个特性，BFS 适合求解一些最少操作的题目。

前面 DFS 部分提到了不管是什么搜索都需要记录和维护状态，其中一个就是节点访问状态以防止环的产生。而 BFS 中我们常常用来求点的最短距离。值得注意的是，有时候我们会使用一个哈希表 dist 来记录从源点到图中其他点的距离。这个 dist 也可以充当防止环产生的功能，这是因为第一次到达一个点后再次到达此点的距离一定比第一次到达大，利用这点就可知道是否是第一次访问了。