—— 基于「模拟消消乐」与「二叉树遍历还原」的实践总结
一、DFS 基本概念
深度优先搜索（DFS，Depth-First Search） 是一种典型的递归/回溯算法思想，其核心特征是：
从起点出发，沿着一条路径不断深入，直到无法继续，再回溯到上一个分支继续探索。
DFS 常见应用场景包括：
- 二维网格搜索（连通块、岛屿问题、消消乐）
- 图遍历
- 树的遍历与重建
- 组合枚举、路径搜索
DFS 的本质通常包含三要素：
- 当前状态
- 可扩展的下一步
- 递归终止条件
二、DFS 示例一：二维网格模拟消消乐
1. 问题描述
给定一个 n × m 的字符棋盘，从指定起点 (r, c) 出发，统计与该起点 字符相同且上下左右连通 的所有格子数量。
这类问题在算法中称为 连通块统计问题。
2. 核心 DFS 思路
- 每个格子视为一个节点
- 上下左右为相邻节点
- 从起点开始，递归访问：
- 字符相同
- 且未访问过的格子
- 使用
visited数组防止重复访问
3. 关键数据结构
static char[,] grid; // 棋盘字符
static bool[,] visited; // 访问标记
static int[] dx = { -1, 1, 0, 0 };
static int[] dy = { 0, 0, -1, 1 };
4. DFS 递归函数解析
static int DFS(int r, int c, char target)
{int cnt = 1; // 当前格子计数for (int i = 0; i < 4; i++){int nr = r + dx[i];int nc = c + dy[i];// 越界检查if (nr < 0 || nr >= n || nc < 0 || nc >= m)continue;// 相同字符且未访问if (grid[nr, nc] == target && !visited[nr, nc]){visited[nr, nc] = true;cnt += DFS(nr, nc, target);}}return cnt;
}
5. DFS 执行流程总结
- 标记当前格子为已访问
- 向四个方向扩展
- 满足条件则继续递归
- 无路可走时返回
- 汇总所有子递归的计数
6. 算法特性
- 时间复杂度：
O(n * m) - 空间复杂度：
O(n * m)（递归栈 + visited）
三、DFS 示例二：已知中序 + 后序，求先序遍历
1. 问题描述
已知一棵二叉树的：
- 中序遍历（Inorder）
- 后序遍历（Postorder）
要求输出其 先序遍历（Preorder）
2. 二叉树遍历性质
| 遍历方式 | 顺序 |
|---|---|
| 先序 | 根 → 左 → 右 |
| 中序 | 左 → 根 → 右 |
| 后序 | 左 → 右 → 根 |
| 关键规律： |
后序遍历的最后一个节点，一定是当前子树的根节点。
3. DFS 递归拆解思路
-
从后序序列中取出根节点
-
在中序序列中定位根节点位置
-
划分左右子树：
- 左子树长度 = 根在中序中的索引
-
对左右子树递归求先序
-
拼接结果：
根 + 左先序 + 右先序
4. 递归实现代码解析
static string FindPreorder(string inorder, string postorder)
{if (inorder.Length == 0)return "";// 根节点char root = postorder[postorder.Length - 1];// 中序中找到根int idx = inorder.IndexOf(root);// 左右子树中序string leftIn = inorder.Substring(0, idx);string rightIn = inorder.Substring(idx + 1);// 左右子树后序string leftPost = postorder.Substring(0, idx);string rightPost = postorder.Substring(idx, postorder.Length - 1 - idx);// 递归return root+ FindPreorder(leftIn, leftPost)+ FindPreorder(rightIn, rightPost);
}
5. DFS 在树问题中的本质
- 每一次递归解决的是一个 子树
- 子问题结构完全相同
- 非常适合 DFS 的「分治 + 递归」模型
四、两类 DFS 问题的对比总结
| 对比项 | 网格消消乐 | 二叉树遍历 |
|---|---|---|
| 数据结构 | 二维数组 | 树（隐式） |
| 相邻关系 | 上下左右 | 左右子树 |
| visited | 必须 | 不需要 |
| 递归终止 | 无可扩展邻居 | 空子树 |
| 返回值 | 连通块数量 | 遍历字符串 |
五、DFS 解题通用模板
1. 明确当前状态（位置 / 子树）
2. 标记访问（如需要）
3. 枚举下一步选择
4. 判断是否合法
5. 递归深入
6. 汇总结果并返回
六、工程级 DFS：连通块预处理版消消乐（高频查询优化）
在真实业务或竞赛环境中，DFS 往往并不是“只跑一次”。
当 棋盘固定、查询次数 m 很大 时，若每次点击都重新 DFS / BFS，将导致不可接受的时间复杂度。
为此，可以引入 连通块预处理（Connected Component Preprocessing） 思想。
1. 问题升级背景
- 棋盘大小：
n × n - 点击次数：
m（可达 10^5） - 每次点击：询问该格子所属的消除连通块大小
- 棋盘 不发生变化
目标：
用一次 DFS / BFS 预处理，支持 O(1) 次查询。
2. 核心设计思想
将 DFS 的“遍历行为”与“查询行为”解耦：
| 阶段 | 作用 |
|---|---|
| 预处理 | 用 DFS 标记所有连通块 |
| 查询 | 直接 O(1) 返回答案 |
3. 关键数据结构设计
int[,] grid; // 棋盘颜色
int[,] compId; // 每个格子所属的连通块编号
int[] compSize; // 每个连通块包含的格子数量
含义说明：
compId[x][y] = k
表示(x, y)属于第k个连通块compSize[k]
表示该id的格子总数
4. DFS 预处理核心逻辑
static void DFS(int x, int y, int id)
{// 标记当前格子属于 id 连通块compId[x, y] = id;compSize[id]++;for (int i = 0; i < 4; i++){int nx = x + dx[i];int ny = y + dy[i];// 越界检查if (nx < 0 || nx >= n || ny < 0 || ny >= n)continue;// 相同颜色 + 未访问if (grid[x, y] == grid[nx, ny] && compId[nx, ny] == 0){DFS(nx, ny, id);}}
}
5. 预处理流程拆解
for 每一个格子 (i, j)if compId[i][j] == 0compCnt++DFS(i, j, compCnt)
解释：
compCnt：当前连通块编号- 每个格子只会被 DFS 访问一次
- 每个连通块都会被完整统计大小
6. 查询阶段（O(1)）
int id = compId[x][y];
Console.WriteLine(compSize[id]);
查询无需 DFS / BFS，直接查表即可。
7. DFS 与 BFS 在该模型下的对比
| 对比项 | DFS | BFS |
|---|---|---|
| 实现复杂度 | 更简洁 | 稍复杂 |
| 代码可读性 | 高 | 中 |
| 栈风险 | 有（深递归） | 无 |
| 工程稳定性 | 中 | 高 |
| 时间复杂度 | O(n²) | O(n²) |
| 结论： |
- 数据规模较大、递归深度不可控 → 优先 BFS
- 教学 / 思维训练 / 树结构 → DFS 更直观
8. 复杂度分析
设 N = n × n
- 预处理时间复杂度：
O(N) - 单次查询时间复杂度：
O(1) - 总时间复杂度：
O(N + m) - 空间复杂度：
O(N)
9. 本质总结
该 DFS 并非“暴力搜索”，而是：
一次 DFS，换取所有查询的常数时间响应
这是 DFS 在工程与竞赛中最重要的进阶用法之一。