什么是廣度優先搜索 (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)，并在實際項目中發揮其優勢。謝謝閱讀！

---

希望這份博客能夠幫助到你。如果有其他需要修改或添加的地方，請隨時告訴我。

?