# BFS 和 DFS

抛开代码细节，从思维模型和数据结构本质上来看看这俩的区别。

# 1. 思维模型的区别：一条路走到黑 vs. 层层剥洋葱

DFS（深度优先）：不撞南墙不回头
- 逻辑：它的策略是 “纵向挖掘”。就像走迷宫，选定一条路一直往下走，直到走到死胡同（叶子节点），然后退回来（回溯），再换另一条路继续钻。
- 在这道题里：它的思路是 “递归”。我想知道我的深度，我就问我的左孩子和右孩子：“你俩谁深？” 它俩再分别问它们的孩子…… 一直问到底。
- 核心公式： $Height = \max(Left, Right) + 1$ 。
BFS（广度优先）：地毯式搜索
- 逻辑：它的策略是 “横向铺开”。就像水波纹扩散，或者剥洋葱，先把第 1 层看完，再看第 2 层，严防死守，绝不漏掉这一层的任何一个节点，才准进入下一层。
- 在这道题里：它的思路是 “数层数”。我不管哪条路最深，我就一层一层地剥。剥完第一层，计数器 +1；剥完第二层，计数器再 +1。直到剥到最后一层没东西了，计数器的数字就是最大深度。

# 2. 数据结构的底层差异：Stack vs. Queue

这才是导致你觉得 BFS 代码 “懵” 的根本原因。

DFS 隐式使用了 “栈” (Stack)：
你写的递归代码，实际上是利用了系统的函数调用栈。你不需要自己去 push 或 pop ，编译器帮你做了。所以代码看起来特别干净。
BFS 显式使用了 “队列” (Queue)：
BFS 没有递归可以用，它必须手动维护一个队列。
- 第一步：把根节点扔进队列。
- 第二步：把这一层的所有节点拿出来（出队），同时把它们的孩子扔进去（入队）。
- 循环：每做完一轮 “出队 + 入队” 的操作，就代表遍历完了一整层，深度就 +1。

# 为什么 BFS 看起来有点 “蠢”？

在 “求最大深度” 这道题上，BFS 确实显得笨重。因为它要维护队列，还要写循环，还要记录当前层有多少个元素，非常繁琐。

但是，BFS 有它无可替代的场景：求最短路径。

想象一下，如果这棵树不是求最大深度，而是问你 “离根节点最近的叶子节点在哪里”（最小深度）？

DFS 依然会傻傻地把一条路走到最深，可能要把大半棵树都遍历完才能找到那个很浅的答案。
BFS 只要铺开几层，一旦遇到第一个叶子节点，立马就能停止，返回答案。这就是 BFS 的高光时刻。

# 总结一下

DFS = 钻头。适合这种需要遍历到底、或者逻辑上有递归性质的题目（比如最大深度、前后序遍历）。
BFS = 雷达。适合找 “最近”、“层级” 相关的题目（比如层序遍历、最小深度）。

这道题你用 DFS 是完全正确的选择，既优雅又符合直觉。BFS 在这里更多是为了展示一种 “按层扫描” 的逻辑能力，属于 “虽然麻烦但必须要会” 的基本功。

# BFS

# 1091 二进制矩阵中的最短路径

一个是我（结合题解）的写法：

	int shortestPathBinaryMatrix(vector<vector<int>> &grid)
	{
	int n = grid.size();
	if (grid[0][0] == 1)
	{
	return -1;
	}
	queue<pair<int, int>> a;
	a.push({0, 0});
	vector<vector<int>> dis(n, vector<int>(n, INT_MAX));
	dis[0][0] = 1;

	while (a.size() != 0)
	{

	auto [x, y] = a.front();
	a.pop();
	if (x == n - 1 && y == n - 1)
	{
	return dis[n - 1][n - 1];
	}

	for (int dx = -1; dx <= 1; dx++)
	{
	for (int dy = -1; dy <= 1; dy++)
	{
	int xnew = x + dx;
	int ynew = y + dy;
	if (xnew < 0 \|\| xnew >= n \|\| ynew < 0 \|\| ynew >= n)
	{
	continue;
	}
	if (grid[xnew][ynew] == 1 \|\| dis[xnew][ynew] <= dis[x][y] + 1)
	{
	continue;
	}
	dis[xnew][ynew] = dis[x][y] + 1;
	a.push({xnew, ynew});
	}
	}
	}
	return -1;
	}

但是这个只击败了 22% 的人。官解试了一下也只有 18% 的人，说明就是写的不行。
问了 gemini，给了我一个优化的写法，击败了 85%。但是我又想到我一开始的解法：不记步数，直接看循环次数，得出最短路径。
既然是无向图后面遍历到的点经过的距离是前一个的加一，我为什么不直接看循环次数呢？还那么麻烦开个距离二维数组。
写了一个优化后的解法（当然时间复杂度一开始是击败了 30%，后面 gemini 帮我进行了一个小的优化，最终时间复杂度击败 85%，空间击败 97%！）

	int shortestPathBinaryMatrix(vector<vector<int>> &grid) {
	int n = grid.size();
	const int p[8][2] = <!--swig0-->;
	if (grid[0][0] == 1 \|\| grid[n - 1][n - 1] == 1) {
	return -1;
	}
	if (n == 1) {
	return 1;
	}
	queue<pair<int, int>> a;
	a.push({0, 0});
	grid[0][0] = 1;
	int sum = 1;

	while (a.size() != 0) {
	int m = a.size();
	for (int i = 0; i < m; i++) {
	auto [x, y] = a.front();
	a.pop();
	for (int j = 0; j < 8; j++) {
	int xnew = x + p[j][0];
	int ynew = y + p[j][1];
	if (xnew < 0 \|\| xnew >= n \|\| ynew < 0 \|\| ynew >= n) {
	continue;
	}
	if (grid[xnew][ynew] == 1) {
	continue;
	}
	if (xnew == n - 1 && ynew == n - 1) {
	// 核心调整：检测到符合直接退出！记住这里是 sum+1 因为多跳了一步。
	return sum + 1;
	}
	a.push({xnew, ynew});
	grid[xnew][ynew] = 1;
	}
	}
	sum++;
	}
	return -1;
	}

这就是层序遍历。

原创