我們一起聊聊十五周算法—BFS

作者：前端點線面 2023-05-08 07:32:03

開發前端

「BFS相對于DFS的最主要的區別是：BFS找到的路徑一定是最短的，但代價就是空間復雜度比DFS大很多。」

「BFS的核心思想是把一些問題抽象成圖，從一個點開始，向四周開始擴散。一般來說，寫BFS算法都是用隊列這種數據結構，每次將一個節點周圍的所有節點加入隊列。」

「BFS相對于DFS的最主要的區別是：BFS找到的路徑一定是最短的，但代價就是空間復雜度比DFS大很多。」

「BFS出現的常見場景：問題的本質就是讓你在一幅圖中找到從起點start到終點target的最近距離」

二叉樹的最小深度

給定一個二叉樹，找出其最小深度。

最小深度是從根節點到最近葉子節點的最短路徑上的節點數量。

說明：葉子節點是指沒有子節點的節點。

示例 1：

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

// 找最短路徑，用BFS
// 1. 首先明確起點start和終點target是什么？
// 起點就是root根節點，終點就是最靠近根節點的那個葉子節點
// 2、 怎么判斷達到了終點
// 葉子節點就是兩個子節點都是null的節點

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;

            // 遍歷當前存在隊列中的數據
            for (let i = 0; i < size; i++) {
                const cur = queue.shift();

                // 將左右子節點存入隊列
                if (cur.left) {
                    queue.push(cur.left);
                }
                if (cur.right) {
                    queue.push(cur.right);
                }

                if (cur.left === null && cur.right === null) {
                    return depth;
                }
            }

            // 遍歷完一層之后增加步數
            depth++;
        }

        return depth;
    }

    return bfs(root);
}

填充每個節點的下一個右側節點指針

給定一個完美二叉樹，其所有葉子節點都在同一層，每個父節點都有兩個子節點。二叉樹定義如下：

struct Node { int val; Node *left; Node *right; Node *next; } 填充它的每個 next 指針，讓這個指針指向其下一個右側節點。如果找不到下一個右側節點，則將 next 指針設置為 NULL。

初始狀態下，所有 next 指針都被設置為 NULL。

示例 1：

輸入：root = [1,2,3,4,5,6,7] 輸出：[1,#,2,3,#,4,5,6,7,#] 解釋：給定二叉樹如圖 A 所示，你的函數應該填充它的每個 next 指針，以指向其下一個右側節點，如圖 B 所示。序列化的輸出按層序遍歷排列，同一層節點由 next 指針連接，'#' 標志著每一層的結束

// 典型的通過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();
            // 進行連接
            if (i === size - 1) {
                preNode.next = null;
            } else {
                preNode.next = list[0];
            }
            // 獲取下一個元素，將內容填充到棧中
            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));

責任編輯：武曉燕來源：前端點線面