广度优先搜索（BFS）

在树的遍历方式中，深度优先搜索法与广度优先搜索算是最常用的手段了。这一篇来聊聊广度优先搜索。

广度优先搜索，也叫树的层序遍历法，即每一次遍历处理一层的节点。

其核心数据结构是队列。我们需要维护一个队列，每次从队尾取出需要遍历的节点，并在逻辑结束后将遍历节点的子节点入队，作为下一层遍历时的节点使用。

这里需要注意的是，我们每次开始一个新的层级遍历前，循环次数一定要锁死为目前队列的长度。这是因为在遍历过程中，我们会将子节点入队，从而改变队列的长度，影响当前层级循环次数的判断。

有时，我们需要维护一个visited变量，用于记录访问过的节点。并在节点入队前判断，当前节点是否已经被遍历过，从而减少重复遍历的发生。

BFS 的算法框架大致如下：

const queue = [root];
let step = 1;

const visited: Record<node, boolean> = {}

while(queue.length) {
  let len = queue.length;
  while(len--) {
    const node = queue.shift();
    // 若找到节点，则返回当前层级，亦或是其他符合要求的输出
    if(node 符合要求) return step;

    // 将子节点入队，等待下一轮遍历
    if(node.left && !visited[node.left]) {
      // 将当前节点设置为已访问，防止重复遍历
      visited[node.right] = true;
      queue.push(node.left);
    }
    if(node.right && !visited[node.right]) {
      // 将当前节点设置为已访问，防止重复遍历
      visited[node.right] = true;
      queue.push(node.right);
    }
  }
  // 遍历完一层，计数器+1
  step += 1;
}
// 说明此时无可达路径
return -1;

对于二维矩阵的广度优先搜索，本质上是一个多叉树的BFS。

我们可以维护一个方向数组（根据题目要求，可以为二向、四向或是八向），表示每一次可选子节点的个数，也即多叉树的叉数。

每次搜索完当前节点，需要将子节点入队时，根据方向，分别入队所有子结果。

const queue = [root];
let step = 1;

const visited: Record<node, boolean> = {}

// 定义一个方向数组，这里以四向为例
const directions = [
  [0, 1],
  [0, -1],
  [1, 0],
  [-1, 0]
];

while(queue.length) {
  let len = queue.length;
  while(len--) {
    const [x, y] = queue.shift();
    // 若找到节点，则返回当前层级，亦或是其他符合要求的输出
    if(x, y 符合要求) return step;

    for (const [directX, directY] of directions) {
      const curr = [x + directX, y + directY];

      // 异常情况剪枝
      if(visited[curr] || curr 越界 || curr 不满足要求) continue;
      // 标记当前节点已访问
      visited[curr] = true;

      // ...此处可以更新记录或是其他操作

      // 将子节点入队，等待下一轮遍历
      queue.push(curr);
    }
  }
  // 遍历完一层，计数器+1
  step += 1;
}
// 说明此时无可达路径
return -1;

我们可以注意到，BFS算法最佳的使用场景是：求出通往某节点的最短路径。

因为求出时的预期代价比使用DFS要小，如果时DFS来做，必须要深搜完所有节点才能得出结论。而对于BFS来说，只要第一次搜索到目标节点，则该路径一定是最短的，可以直接返回。

但是，相比于DFS的递归式，BFS需要多维护一个队列来存储每一层级的数据，在空间复杂度上的表现通常花费较多。

题型参考

1. 102. 二叉树的层序遍历
2. 111. 二叉树的最小深度
3. 127. 单词接龙