Data structure

資料結構：二元樹（二叉樹）的後序遍歷（Postorder Traversal）

主題

後序遍歷（Postorder Traversal）是二叉樹遍歷的一種方式。
其中節點的順序是先訪問左子樹，然後訪問右子樹，最後訪問根節點。

以下是後序遍歷的過程：

  1. 檢查當前節點是否為空。如果是空節點，則返回上一層。
  2. 從當前節點開始，先遞歸地後序遍歷左子樹。
  3. 接著，遞歸地後序遍歷右子樹。
  4. 最後，訪問當前節點。

這個遍歷過程可以使用遞歸或堆疊來實現。

以下是一個使用遞歸的後序遍歷的範例： 假設有以下二叉樹：

       A
      / \
     B   C
    / \   \
   D   E   F

後序遍歷的結果將是：D, E, B, F, C, A。

過程如下：

  1. 從根節點 A 開始：
    • 遞歸地後序遍歷左子樹 B。
      • 遞歸地後序遍歷左子樹 D。
        • D 為葉子節點，訪問 D。
      • 遞歸地後序遍歷右子樹 E。
        • E 為葉子節點，訪問 E。
      • 訪問 B。
    • 遞歸地後序遍歷右子樹 C。
      • 遞歸地後序遍歷右子樹 F。
        • F 為葉子節點，訪問 F。
      • 訪問 C。
    • 訪問 A。

因此，後序遍歷的結果為 D, E, B, F, C, A。

實作

// 定義二元樹節點的結構
class TreeNode {
    constructor(val, left, right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

// 後序遍歷函數
function postOrderTraversal(root) {
    let result = [];
    traversal(root, result);
    return result;
}

// 後序遍歷函數，使用遞迴（recursion）來實作。
function traversal(root, result) {
    if (root === null) {
        return;
    }

    // 遍歷左子樹
    traversal(root.left, result);

    // 遍歷右子樹
    traversal(root.right, result);

    // 儲存根節點的值
    result.push(root.val);
}

// 建立二元樹
/**
 *           4
 *          /  \
 *        2     6
 *       / \    / \
 *      1   3  5   7
 *     / \ / \/ \ / \
 *    n  n n nn n n  n
 */
const root = new TreeNode(
    4,
    new TreeNode(2, new TreeNode(1, null, null), new TreeNode(3, null, null)),
    new TreeNode(6, new TreeNode(5, null, null), new TreeNode(7, null, null))
);

// 呼叫後序遍歷函數
const postOrderTraversalResult = postOrderTraversal(root);
console.log(postOrderTraversalResult); // 輸出：[1, 3, 2, 5, 7, 6, 4]

最後，如果你覺得我的分享對你有幫助，請給予我一個愛心，並且分享這篇文章，這將是對我最大的鼓勵！