我們一起聊聊十五周算法—BFS
「BFS的核心思想是把一些問題抽象成圖，從一個點開始，向四周開始擴(kuò)散。一般來說，寫B(tài)FS算法都是用隊列這種數(shù)據(jù)結(jié)構(gòu)，每次將一個節(jié)點周圍的所有節(jié)點加入隊列。」
「BFS相對于DFS的最主要的區(qū)別是：BFS找到的路徑一定是最短的，但代價就是空間復(fù)雜度比DFS大很多。」
「BFS出現(xiàn)的常見場景：問題的本質(zhì)就是讓你在一幅圖中找到從起點start到終點target的最近距離」
二叉樹的最小深度
給定一個二叉樹，找出其最小深度。
最小深度是從根節(jié)點到最近葉子節(jié)點的最短路徑上的節(jié)點數(shù)量。
說明：葉子節(jié)點是指沒有子節(jié)點的節(jié)點。
示例 1：
輸入：root = [3,9,20,null,null,15,7] 輸出：2
// 找最短路徑，用BFS
// 1. 首先明確起點start和終點target是什么？
// 起點就是root根節(jié)點，終點就是最靠近根節(jié)點的那個葉子節(jié)點
// 2、 怎么判斷達(dá)到了終點
// 葉子節(jié)點就是兩個子節(jié)點都是null的節(jié)點
function minDepth(root) {
const bfs = (root) => {
if (!root) {
return 0;
}
// root本身就是一層，depth初始化為1
let depth = 1;
const queue = [root];
while (queue.length > 0) {
const size = queue.length;
// 遍歷當(dāng)前存在隊列中的數(shù)據(jù)
for (let i = 0; i < size; i++) {
const cur = queue.shift();
// 將左右子節(jié)點存入隊列
if (cur.left) {
queue.push(cur.left);
}
if (cur.right) {
queue.push(cur.right);
}
if (cur.left === null && cur.right === null) {
return depth;
}
}
// 遍歷完一層之后增加步數(shù)
depth++;
}
return depth;
}
return bfs(root);
}填充每個節(jié)點的下一個右側(cè)節(jié)點指針
給定一個 完美二叉樹 ，其所有葉子節(jié)點都在同一層，每個父節(jié)點都有兩個子節(jié)點。二叉樹定義如下：
struct Node { int val; Node *left; Node *right; Node *next; } 填充它的每個 next 指針，讓這個指針指向其下一個右側(cè)節(jié)點。如果找不到下一個右側(cè)節(jié)點，則將 next 指針設(shè)置為 NULL。
初始狀態(tài)下，所有 next 指針都被設(shè)置為 NULL。
示例 1：
輸入：root = [1,2,3,4,5,6,7] 輸出：[1,#,2,3,#,4,5,6,7,#] 解釋：給定二叉樹如圖 A 所示，你的函數(shù)應(yīng)該填充它的每個 next 指針，以指向其下一個右側(cè)節(jié)點，如圖 B 所示。序列化的輸出按層序遍歷排列，同一層節(jié)點由 next 指針連接，'#' 標(biāo)志著每一層的結(jié)束
// 典型的通過BFS解決
function connect(root) {
if (root === null) {
return root;
}
const list = [root];
while (list.length > 0) {
const size = list.length;
for (let i = 0; i < size; i++) {
const preNode = list.shift();
// 進(jìn)行連接
if (i === size - 1) {
preNode.next = null;
} else {
preNode.next = list[0];
}
// 獲取下一個元素，將內(nèi)容填充到棧中
preNode.left && list.push(preNode.left);
preNode.right && list.push(preNode.right);
}
}
return root;
}
const root = {
val: 1,
left: {
val: 2,
left: null,
right: null
},
right: {
val: 3,
left: null,
right: null
}
};
console.log(connect(root));
