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