學習資源

https://labuladong.online/algo/data-structure-basic/binary-tree-traverse-basic/#层序遍历-bfs

學習記錄

今天是學習的第 21 天，主要學習了二叉樹的層序遍歷（BFS）：

DFS 和 BFS 的區別

二叉樹的層序遍歷，就是一層一層地遍歷二叉樹：

       1          ← 第 1 層
      / \
     2   3        ← 第 2 層
    / \   \
   4   5   6      ← 第 3 層

層序遍歷結果： 1 → 2 → 3 → 4 → 5 → 6

寫法一

第一種寫法較簡單，就是利用隊列的概念，每次將隊頭元素取出來，然後把它的左右子節點加入隊列。

但缺點是無法知道當前節點所在的層數，而知道節點的層數是一個常見的需求。

class TreeNode {
    constructor(val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

var levelOrderTraverse = function(root) {
    if (root === null) {
        return;
    }
    var q = [];
    q.push(root);
    while (q.length !== 0) {
        var cur = q.shift();
        // 訪問 cur 節點
        console.log(cur.val);

        // 把 cur 的左右子節點加入隊列
        if (cur.left !== null) {
            q.push(cur.left);
        }
        if (cur.right !== null) {
            q.push(cur.right);
        }
    }
}

// 範例：建立一棵滿二叉樹（高度為 3）
//        1
//      /   \
//     2     3
//    / \   / \
//   4   5 6   7

const root = new TreeNode(1);

root.left = new TreeNode(2);
root.right = new TreeNode(3);

root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
root.right.left = new TreeNode(6);
root.right.right = new TreeNode(7);

levelOrderTraverse(root);
// 執行順序是 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7

寫法二

寫法二是將寫法一做了一些調整，讓我們能夠知道當前節點所在的層數，也是比較常用的寫法。

class TreeNode {
    constructor(val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

var levelOrderTraverse = function(root) {
    if (root === null) {
        return;
    }
    let q = [];
    q.push(root);
    // 記錄當前遍歷到的層數（根節點是為第 1 層）
    let depth = 1;

    while (q.length !== 0) {
        let sz = q.length;
        for (let i = 0; i < sz; i++) {
            let cur = q.shift();
            // 訪問 cur 節點，同時知道它所在的層數
            console.log("depth = " + depth + ", val = " + cur.val);

            // 把 cur 的左右子節點加入隊列
            if (cur.left !== null) {
                q.push(cur.left);
            }
            if (cur.right !== null) {
                q.push(cur.right);
            }
        }
        depth++;
    }
};

// 範例：建立一棵滿二叉樹（高度為 3）
//        1
//      /   \
//     2     3
//    / \   / \
//   4   5 6   7

const root = new TreeNode(1);

root.left = new TreeNode(2);
root.right = new TreeNode(3);

root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
root.right.left = new TreeNode(6);
root.right.right = new TreeNode(7);

levelOrderTraverse(root);
// depth = 1, val = 1
// depth = 2, val = 2
// depth = 2, val = 3
// depth = 3, val = 4
// depth = 3, val = 5
// depth = 3, val = 6
// depth = 3, val = 7

寫法三

寫法三是在寫法一的基礎上添加了一個 State 類，讓每個節點自己負責維護自己的路徑權重和。

class TreeNode {
    constructor(val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

function State(node, depth) {
    this.node = node;
    this.depth = depth;
}

var levelOrderTraverse = function(root) {
    if (root === null) {
        return;
    }
    // @visualize bfs
    var q = [];
    // 根節點的路徑權重和是 1
    q.push(new State(root, 1));

    while (q.length !== 0) {
        var cur = q.shift();
        // 訪問 cur 節點，同時知道它的路徑權重和
        console.log("depth = " + cur.depth + ", val = " + cur.node.val);

        // 把 cur 的左右子節點加入隊列
        if (cur.node.left !== null) {
            q.push(new State(cur.node.left, cur.depth + 1));
        }
        if (cur.node.right !== null) {
            q.push(new State(cur.node.right, cur.depth + 1));
        }
    }
};

// 範例：建立一棵滿二叉樹（高度為 3）
//        1
//      /   \
//     2     3
//    / \   / \
//   4   5 6   7

const root = new TreeNode(1);

root.left = new TreeNode(2);
root.right = new TreeNode(3);

root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
root.right.left = new TreeNode(6);
root.right.right = new TreeNode(7);

levelOrderTraverse(root);
// depth = 1, val = 1
// depth = 2, val = 2
// depth = 2, val = 3
// depth = 3, val = 4
// depth = 3, val = 5
// depth = 3, val = 6
// depth = 3, val = 7

學習總結

• 二叉樹的層序遍歷，就是一層一層地遍歷二叉樹：
• 層序遍歷有多種寫法，但是第二種寫法就能滿足大部分情境