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

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

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

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

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

BFS 算法的基本步骤 

1. 准备工作：

   • 创建一个队列，将起点放入队列
   • 创建一个访问标记，标记起点已被访问

2. 循环扩展：

   • 当队列不为空时，取出队列头部元素
   • 检查该元素是否是目标
   • 如果不是，将该元素的所有未访问邻居加入队列
   • 标记这些邻居为已访问

3. 结束条件：

   • 找到目标元素，返回结果
   • 队列为空，说明无法到达目标

BFS vs DFS 

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

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

102.二叉树的层序遍历

题目描述

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

解题思路

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

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

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

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

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

 例题代码

/**
 * 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;
    }
}

执行速度

希望本文能够帮助读者更深入地理解广度优先搜索(BFS)，并在实际项目中发挥其优势。谢谢阅读！

希望这份博客能够帮助到你。如果有其他需要修改或添加的地方，请随时告诉我。