學習資源

https://labuladong.online/algo/data-structure-basic/n-ary-tree-traverse-basic/

學習記錄

今天是學習的第 24 天，主要學習了多叉樹的遞歸遍歷（DFS）：

在苦痛之路 Day 21 - 二叉樹的遞歸遍歷（DFS）中，有介紹到二叉樹的遞歸遍歷，讓我們來看看多叉樹的遞歸遍歷是如何做到。

這是一個二叉樹的節點，每一個節點會有 left、right 兩個子節點：

var TreeNode = function(val) {
    this.val = val;
    this.left = null;
    this.right = null;
};

而這是一個多叉樹的節點，每一個節點會有任意個子節點：

var Node = function(val) {
    this.val = val;
    this.children = [];
}

遞歸遍歷（DFS）

讓我們複習一下，這是二叉樹的遍歷框架：

// 二叉樹的遍歷框架
var traverse = function(root) {
    if (root === null) {
        return;
    }
    // 前序位置
    traverse(root.left);
    // 中序位置
    traverse(root.right);
    // 後序位置
};

這是一個多叉樹的遍歷框架，和二叉樹遍歷框架的差別在於沒有中序位置：

// 多叉樹的遍歷框架
var traverse = function(root) {
    if (root === null) {
        return;
    }
    // 前序位置
    for (var i = 0; i < root.children.length; i++) {
        traverse(root.children[i]);
    }
    // 後序位置
};

讓我們來看看實際的遍歷順序：

var preorderResult = [];
var postorderResult = [];

var traverse = function(root) {
    if (root === null) {
        return;
    }
    // 前序位置
    preorderResult.push(root.val);
    for (var i = 0; i < root.children.length; i++) {
        traverse(root.children[i]);
    }
    // 後序位置
    postorderResult.push(root.val);
};

// 建立一棵多叉樹
//        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;
traverse(root);

console.log(preorderResult); // [1, 3, 5, 6, 2, 4]
console.log(postorderResult); // [5, 6, 3, 2, 4, 1]

學習總結

• 多叉樹的節點，每一個節點會有任意個子節點
• 多叉樹的遍歷框架沒有中序位置