如同Queue章節提到，BFS使用 Queue依序處理每層節點，所以適合

1. 統計每層節點資訊，例如：平均值、最大值、最右邊/最左邊。
2. 最短路徑，BFS 保證第一次到達某個節點時，就是最短距離。

DFS V.S. BFS

DFS：適合解全域最佳解、路徑類型。

BFS：適合最短路徑、分層統計類型。

照慣例我們刷個幾題適合用BFS來解的題目

BFS遍歷

Leecode 103. Binary Tree Zigzag Level Order Traversal

題目：給一顆樹依層分類奇數層由左而右排，偶數層由右向左排

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

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

解法：使用BFS逐層找節點，並依照目前的層數決定排序。

// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }
// 
// impl TreeNode {
//   #[inline]
//   pub fn new(val: i32) -> Self {
//     TreeNode {
//       val,
//       left: None,
//       right: None
//     }
//   }
// }
// BFS 
// push root to queue level=1
// for i in 0..queue.len() get current level node and push subtree
// after itor push current nodes and level+=1
// init root=[3,9,20,null,null,15,7] queue=[] ans:[]
// root=[9,20,null,null,15,7] queue=[3] ans:[] level=1
// root=[null,null,15,7] queue=[9,20] ans:[[3]] level=2
// root=[] queue=[15,7] ans:[[3],[20,9]] level=3
// root=[] queue=[] ans:[[3],[20,9],[15,7]] level=4
// finish return ans
use std::rc::Rc;
use std::cell::RefCell;
use std::collections::VecDeque;
impl Solution {
    pub fn zigzag_level_order(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<Vec<i32>> {
        let Some(root)=root else{ return vec![]};
        let mut deque = VecDeque::new();
        let mut level =1;
        let mut return_ans=Vec::new();

        deque.push_back(root);
        while deque.len()>0 {
            let level_size = deque.len();
            let mut level_ans=Vec::new();
            for i in 0..level_size {
                let Some(node)=deque.pop_front() else { continue};
                let rc=node.borrow();
                level_ans.push(rc.val);
                if(rc.left.is_some()){
                    deque.push_back(rc.left.clone().unwrap());
                }
                if(rc.right.is_some()){
                    deque.push_back(rc.right.clone().unwrap());
                }
            }
            if(level%2==0){
                level_ans.reverse();
            }
            return_ans.push(level_ans);
            level+=1;
        }
        return_ans
    }
}

BFS最短路徑

Leetcode 111. Minimum Depth of Binary Tree

題目：找到離跟節點最短的葉節點，回傳他在哪一層

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

輸出：2

做法：用BFS去找第一個葉節點，能確保他是最短路徑並回傳他在哪一層

// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }
// 
// impl TreeNode {
//   #[inline]
//   pub fn new(val: i32) -> Self {
//     TreeNode {
//       val,
//       left: None,
//       right: None
//     }
//   }
// }
// use BFS find shortest leaf
// init root = [3,9,20,null,null,15,7] queue:[] level=0
// root = [9,20,null,null,15,7] queue:[3] level:1 if sub tree in left or right push to queue else return level
// root = [null,null,15,7] queue:[9,20] level:2 if sub tree in left or right push to queue else return level
// 9 is leaf node return level=2

use std::rc::Rc;
use std::cell::RefCell;
use std::collections::VecDeque;
impl Solution {
    pub fn min_depth(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {        
        let mut deque=VecDeque::new();
        let mut level=0;
        let Some(node)=root else { return 0 };
        deque.push_back(node);
        level+=1;
        while deque.len()>0 {
            let layer_size = deque.len();
            for i in 0..layer_size {
                let n = deque.pop_front().expect("must have node");
                let rc = n.borrow();
                if(rc.left.clone().is_none() & rc.right.clone().is_none()){
                    return level
                }
                if(rc.left.clone().is_some()){
                    deque.push_back(rc.left.clone().expect("must have node"));
                }
                if(rc.right.clone().is_some()){
                    deque.push_back(rc.right.clone().expect("must have node"));
                }
            }
            level+=1;
        }
        0
    }
}

BFS 視圖(view)

Leetcode 199. Binary Tree Right Side View

題目：你從右邊看這顆樹，他會長什麼樣

輸入：root = [1,2,3,null,5,null,4]

輸出：[1,3,4]

做法：由右這顆樹看到的為每層最後一個節點，因此只要記錄每層最後一個節點就好。

// #[derive(Debug, PartialEq, Eq)]
// Definition for a binary tree node.
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }
// 
// impl TreeNode {
//   #[inline]
//   pub fn new(val: i32) -> Self {
//     TreeNode {
//       val,
//       left: None,
//       right: None
//     }
//   }
// }
//init root = [1,2,3,null,5,null,4] queue=[] level=0 last[]
//root = [2,3,null,5,null,4] queue=[1] level=1 last=[]
//root = [null,5,null,4] queue=[2,3] level=2 last=[1]
//root = [] queue=[5,4] level=3 last=[1,3]
//root = [] queue=[] level=4 last=[1,3,4]
//return last [1,3,4]

use std::rc::Rc;
use std::cell::RefCell;
use std::collections::VecDeque;
impl Solution {
    pub fn right_side_view(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
        let Some(node)=root else { return vec![]};

        let mut ans=Vec::new();
        let mut deque=VecDeque::new();
        let mut level=0;

        deque.push_back(node);
        level+=1;
        while deque.len()>0 {
            let layer_size = deque.len();
            for i in 0..layer_size {
                let n = deque.pop_front().expect("must have node");
                let rc=n.borrow();
                if(rc.left.clone().is_some()){
                    deque.push_back(rc.left.clone().expect("must have node"));
                }
                if(rc.right.clone().is_some()){
                    deque.push_back(rc.right.clone().expect("must have node"));
                }
                if(i==layer_size-1){
                    ans.push(rc.val);
                }
            }
            level+=1;
        }
        ans
    }
}

Day26總結

1. BFS適合解最短路徑、統計每層節點資訊。
2. 練習BFS做法