当前位置：首页 > backend >正文

算法学习笔记：3.广度优先搜索 (BFS)——二叉树的层序遍历

backend 2025/6/18 1:07:31

什么是广度优先搜索 (BFS)?

想象一下你在玩一个迷宫游戏，你需要找到从起点到终点的最短路径。广度优先搜索 (BFS) 就像是你在迷宫中逐层探索的过程：

先探索距离起点最近的所有位置
然后探索距离起点第二近的所有位置
以此类推，直到找到终点

BFS 的核心思想是 "逐层扩展"，它使用队列来实现这种扩展方式。

BFS 算法的基本步骤

准备工作：
- 创建一个队列，将起点放入队列
- 创建一个访问标记，标记起点已被访问
循环扩展：
- 当队列不为空时，取出队列头部元素
- 检查该元素是否是目标
- 如果不是，将该元素的所有未访问邻居加入队列
- 标记这些邻居为已访问
结束条件：
- 找到目标元素，返回结果
- 队列为空，说明无法到达目标

BFS vs DFS

BFS 和深度优先搜索 (DFS) 是两种基本的图遍历算法，它们的区别可以用一个形象的比喻来说明：

BFS：像是地毯式搜索，逐层推进，适合找最短路径
DFS：像是一条路走到黑，适合找所有可能的路径

102.二叉树的层序遍历

题目描述

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

解题思路

这道题是 BFS 的典型应用。我们需要：

从根节点开始，逐层遍历二叉树
每一层的节点值放在一个列表中
最终返回这些列表的集合

想象一下，我们有一个队列，就像一个传送带：

首先把根节点放在传送带上
然后每次从传送带上取出一个节点
把这个节点的左右子节点（如果有）放在传送带的末尾
重复这个过程，直到传送带上没有节点

这样就能保证我们按照层次顺序遍历二叉树。

例题代码

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public List<List<Integer>> levelOrder(TreeNode root) {Queue<TreeNode> queue = new LinkedList<>();List<List<Integer>> res = new ArrayList<>();if (root != null) queue.add(root);while (!queue.isEmpty()) {List<Integer> tmp = new ArrayList<>();for(int i = queue.size(); i > 0; i--) {TreeNode node = queue.poll();tmp.add(node.val);if (node.left != null) queue.add(node.left);if (node.right != null) queue.add(node.right);}res.add(tmp);}return res;}
}