學習資源

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

學習記錄

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

二叉樹有兩種遍歷形式：

• 遞歸遍歷：可以衍生出 DFS 算法
• 層序遍歷：可以衍生出 BFS 算法

遞歸遍歷（DFS）

遞歸遍歷的程式碼模板：

// 基本的二叉樹節點
class TreeNode {
    constructor(val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

// 二叉樹的遞歸遍歷框架
var traverse = function(root) {
    if (root === null) {
        return;
    }
    traverse(root.left);
    traverse(root.right);
}

traverse 函式就像一個在二叉樹結構上遊走的指針。

遍歷順序：

1. 先一直往左子節點走（深入左子樹）
2. 遇到空指針（null）後返回
3. 嘗試往右子節點走（探索右子樹）
4. 左右子樹都走完後，返回上一層父節點

前/中/後序遍歷

在 traverse 函式中不同位置寫程式碼，效果是不一樣的。

所謂的前中後序遍歷，指的是在二元樹遍歷框架的不同位置寫程式碼：

// 二叉樹的遍歷框架
var traverse = function(root) {
    if (root === null) {
        return;
    }
    // 前序位置
    traverse(root.left);
    // 中序位置
    traverse(root.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);

traverse(root);

// 前序位置執行順序：1 -> 2 -> 4 -> 5 -> 3 -> 6 -> 7
// 中序位置執行順序：4 -> 2 -> 5 -> 1 -> 6 -> 3 -> 7
// 後序位置執行順序：4 -> 5 -> 2 -> 6 -> 7 -> 3 -> 1

學習總結

• 二叉樹有遞歸遍歷（DFS）和層序遍歷（BFS）兩種遍歷形式
• 在遞歸遍歷的前/中/後序遍歷，程式碼的效果不一樣