之前在stack的深度優先搜尋(Depth First Search)中提到深度優先可以用遞迴和堆疊來解，主要是因為先處理最後進來的值，而在廣度優先則是處理先進來的值。

這跟佇列(queue)先進先出特性吻合，所以解題時可以用佇列(queue)來解，透過樹的層序遍歷，達到層級資料視覺化或是尋找最短路徑。

直接刷個幾題練一下

Leetcode 102. Binary Tree Level Order Traversal

題目：給一顆樹，對每一個level從左到右排序並分群

輸入：root = [3,9,20,null,null,15,7]

輸出：[[3],[9,20],[15,7]]

限制：

• The number of nodes in the tree is in the range [0, 2000].

• -1000 <= Node.val <= 1000

解法：

1. 先把root存到queue

2. 判斷queue中還有沒有值，還有值就帶表樹還沒處理完

3. 依queue長度判斷目前這level有幾個節點，決定要dequeue幾次

4. 將dequeue的值先存倒這層level的暫存向量陣列，並判斷有無左右子樹，如果有就將子樹enqueue到queue中

5. 把這層level所有節點做完後，把暫存的向量陣列記到要回傳的向量陣列

6. 重複2~5直到處理完這顆樹，回傳向量陣列

       3        <- 1th處理
     /   \      
    9    20     <- 2nd處理
        /   \
       15    7  <- 3rd處理

use std::rc::Rc;
use std::cell::RefCell;
use std::collections::VecDeque;

impl Solution {
    pub fn level_order(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<Vec<i32>> {
        //use queue to store node start from root
        let mut queue = VecDeque::new();
        let mut return_vec = Vec::new();
        //dequeue current level node， if dequeue node has child enqueue to queue until queue is empty
        if let Some(root)=root {queue.push_back(root)} else { return vec![]};
        while !queue.is_empty() {

            let mut level_vec = Vec::new(); 
            let mut level_size = queue.len();
            for _ in 0..level_size {
                let Some(node) = queue.pop_front() else { continue };
                let borrow_node = node.borrow();
                level_vec.push(borrow_node.val);
                if (borrow_node.left.clone().is_some()){
                    queue.push_back(borrow_node.left.clone().unwrap());
                }
                if (borrow_node.right.clone().is_some()){
                    queue.push_back(borrow_node.right.clone().unwrap());
                }
            }
            return_vec.push(level_vec);
        }
        return return_vec
    }
}

Leetcode 1091. Shortest Path in Binary Matrix

題目：給一個n*n矩陣，陣列中的值只有0代表可以走的路，1代表牆壁不能走，移動的方向為以自己為九宮格中心往外8個方向，求從矩陣左上角(0,0)移動到右下角(n,n)最短路徑。

輸入：[[0,1],[1,0]]

輸出：2

限制：

• n == grid.length

• n == grid[i].length

• 1 <= n <= 100

• grid[i][j] is 0 or 1

解法1：

1. (0,0)第一格為第一步

2. 往8個方向走合法的有(0,1)、（1,0)、(1,1)，當中只有(1,1)有路所以距離是先前(0,0)距離+1，並複寫到陣列，讓後面走到的人判斷，已經有人捷足先登了或是牆壁不能走。

3. 步驟1、2的概念可以想像成(0,0)先進到queue，起始距離為1

4. 處理佇列(queue)內的物件，判斷

   1. 下一步，8個方向有哪些可以走

   2. 如果可以走的話他們離原點最短距離就是現在的距離+1

   3. 判斷是不是到終點了，如果到了回傳終點的最短距離

use std::collections::VecDeque;

impl Solution {
    pub fn shortest_path_binary_matrix(mut grid: Vec<Vec<i32>>) -> i32 {
        if(grid[0][0]==1){
            return -1
        }
        //use queue store (i,j) grid to do BF, override origin value with distance
        let mut grid = grid.clone();
        let mut queue:VecDeque<(i32,i32)> = VecDeque::new();
        let max_i = grid.len()-1;
        let max_j = grid[0].len()-1;
        const directions:[(i32, i32); 8] = [
            (-1,-1),
            (0,-1),
            (1,-1),
            (-1,0),
            (1,0),
            (-1,1),
            (0,1),
            (1,1)];

        grid[0][0]=1;
        queue.push_back((0,0));

        while !queue.is_empty() {
            let Some((i,j)) = queue.pop_front() else { todo!() };
            let distance =  grid[i as usize][j as usize];
            if(i==max_i as i32 && j==max_j as i32){
                    return distance
            }
            for (dx,dy) in directions {
                if(i+dx<0 as i32|| j+dy<0 as i32|| i+dx>max_i as i32 || j+dy>max_j as i32){
                    continue
                }
                if(grid[(i+dx) as usize][(j+dy) as usize]==0){
                 grid[(i+dx) as usize][(j+dy) as usize] = distance+1;
                 queue.push_back((i+dx,j+dy));
                }
            }
        }
        return -1
    }
}

Day13 總結

1. 廣度優先搜尋BFS用Queue解