後序遍歷」（Post-order Traversal）

 在二元樹中，「後序遍歷」（Post-order Traversal）是按照 左子樹 -> 右子樹 -> 根節點 的順序進行遍歷

Python 程式碼

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def insert_node(root, value):
    if root is None:
        return TreeNode(value)
    if value < root.value:
        root.left = insert_node(root.left, value)
    else:
        root.right = insert_node(root.right, value)
    return root

def build_tree(values):
    root = None
    for value in values:
        root = insert_node(root, value)
    return root

# 後序遍歷函數
def postorder_traversal(node, result):
    if node is not None:
        # 遞迴遍歷左子樹
        postorder_traversal(node.left, result)
        # 遞迴遍歷右子樹
        postorder_traversal(node.right, result)
        # 處理當前節點
        result.append(node.value)
    return result

# 建立二元樹
values = [6, 3, 5, 7, 9, 10, 8, 1, 4, 2]
tree_root = build_tree(values)

# 獲取後序遍歷結果
postorder_result = postorder_traversal(tree_root, [])

# 輸出結果
print("後序遍歷結果:", postorder_result)

---

運行結果

對於給定的數列 [6, 3, 5, 7, 9, 10, 8, 1, 4, 2]，構建的二元樹如下：

          6
       /     \
     3         7
    / \          \
   1   5         9
    \  /        / \
     2 4       8  10

後序遍歷結果是：

[2, 1, 4, 5, 3, 8, 10, 9, 7, 6]

---

說明

1. postorder_traversal 函數:

   • 遞迴處理左子樹 (node.left)。
   • 遞迴處理右子樹 (node.right)。
   • 最後將當前節點的值加入結果列表 (result.append(node.value))。

2. 時間複雜度:

   • 後序遍歷會訪問每個節點一次，時間複雜度為 (O(n))，其中 (n) 是節點數量。

3. 結果檢驗:

   • 結果的順序符合後序遍歷的規則：左 -> 右 -> 根。