學習資源

https://labuladong.online/algo/data-structure-basic/n-ary-tree-traverse-basic/#%E5%B1%82%E5%BA%8F%E9%81%8D%E5%8E%86-bfs

學習記錄

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

在苦痛之路 Day 22 - 二叉樹的層序遍歷（BFS）中，有介紹到二叉樹的層序遍歷，而多叉樹的層序遍歷和二叉樹的層序遍歷一樣，都是透過隊列來實現，只是把二叉樹的左右子節點換成多叉樹的所有子節點。

寫法一

第一種寫法較簡單，但缺點是無法知道當前節點所在的層數：

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 的所有子節點加入隊列
        for (var child of cur.children) {
            q.push(child);
        }
    }
}

// 建立一棵多叉樹
//        1
//      / | \
//     3  2  4
//    / \
//   5   6

var node1 = new Node(1);
var node2 = new Node(2);
var node3 = new Node(3);
var node4 = new Node(4);
var node5 = new Node(5);
var node6 = new Node(6);

node1.children = [node3, node2, node4];
node3.children = [node5, node6];
var root = node1;
levelOrderTraverse(root);
// 執行順序 1 -> 3 -> 2 -> 4 -> 5 -> 6

寫法二

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

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

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

            for (var j = 0; j < cur.children.length; j++) {
                q.push(cur.children[j]);
            }
        }
        depth++;
    }
}

// 建立一棵多叉樹
//        1
//      / | \
//     3  2  4
//    / \
//   5   6

var node1 = new Node(1);
var node2 = new Node(2);
var node3 = new Node(3);
var node4 = new Node(4);
var node5 = new Node(5);
var node6 = new Node(6);

node1.children = [node3, node2, node4];
node3.children = [node5, node6];
var root = node1;
levelOrderTraverse(root);
// depth = 1, val = 1
// depth = 2, val = 3
// depth = 2, val = 2
// depth = 2, val = 4
// depth = 3, val = 5
// depth = 3, val = 6

寫法三

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

// 多叉樹的層序遍歷
// 每個節點自行維護 State 類，記錄深度等訊息
function State(node, depth) {
    this.node = node;
    this.depth = depth;
}

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

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

        for (var i = 0; i < cur.children.length; i++) {
            q.push(new State(cur.children[i], depth + 1));
        }
    }
}

// 建立一棵多叉樹
//        1
//      / | \
//     3  2  4
//    / \
//   5   6

var node1 = new Node(1);
var node2 = new Node(2);
var node3 = new Node(3);
var node4 = new Node(4);
var node5 = new Node(5);
var node6 = new Node(6);

node1.children = [node3, node2, node4];
node3.children = [node5, node6];
var root = node1;
levelOrderTraverse(root);
// depth = 1, val = 1
// depth = 2, val = 3
// depth = 2, val = 2
// depth = 2, val = 4
// depth = 3, val = 5
// depth = 3, val = 6

學習總結

• 多叉樹的層序遍歷和二叉樹的層序遍歷一樣，都是透過隊列來實現