算法模式：广度优先搜索

D瓜哥
算法
算法模式：广度优先搜索

在上一篇文章 算法模式：多路归并 介绍了一种利用堆做链表合并的算法模式。本篇文章，介绍一种即适用于树，又适用于图的的算法模式：广度优先搜索。

广度优先搜索

广度优先搜索既适用于树，又适用于图。除此之外，在处理一些矩阵问题时，也会用到广度优先搜索的思想。当然，也可以把矩阵按照图来理解。

树上的广度优先搜索模式是通过把根节点加到队列中，然后不断遍历直到队列为空。每一次循环中，我们都会把队头结点拿出来（remove），然后对其进行必要的操作。在删除每个节点的同时，其孩子节点，都会被加到队列中。借助于队列数据结构，从而能保证树的节点按照他们的层数打印出来。打印完当前层所有元素，才能执行到下一层。所有这种需要遍历树且需要一层一层遍历的问题，都能用这种模式高效解决。

识别树上的广度优先搜索：

  • 如果你被问到去遍历树，需要按层操作的方式（也称作层序遍历）

LeetCode 102. 二叉树的层序遍历

LeetCode - 102. 二叉树的层序遍历

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。（即逐层地，从左到右访问所有节点）。

示例 1：

0102 00
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]

示例 2：

输入：root = [1]
输出：[[1]]

示例 3：

输入：root = []
输出：[]

提示：

  • 树中节点数目在范围 [0, 2000] 内

  • -1000 <= Node.val <= 1000

思路分析

思路与上述描述类似，这里直接看图：

广度优先搜索
图 1. 广度优先搜索

代码如下：

/**
 * @author D瓜哥 · https://www.diguage.com
 * @since 2025-03-31 07:31:39
 */
public List<List<Integer>> levelOrder(TreeNode root) {
  if (root == null) {
    return Collections.emptyList();
  }
  List<List<Integer>> result = new LinkedList<>();
  Queue<TreeNode> queue = new LinkedList<>();
  queue.offer(root);
  while (!queue.isEmpty()) {
    int size = queue.size();
    List<Integer> level = new ArrayList<>(size);
    for (int i = 0; i < size; i++) {
      TreeNode node = queue.poll();
      level.add(node.val);
      // 将下一层节点，从左到右，依次加入到队列中
      if (node.left != null) {
        queue.offer(node.left);
      }
      if (node.right != null) {
        queue.offer(node.right);
      }
    }
    result.add(level);
  }
  return result;
}