如何返回python二叉樹的后序遍歷

# 如何返回Python二叉樹的后序遍歷

## 引言
二叉樹的后序遍歷（Postorder Traversal）是一種經典的深度優先遍歷算法，其訪問順序遵循"左子樹→右子樹→根節點"的規則。本文將詳細講解在Python中實現二叉樹后序遍歷的多種方法，包括遞歸法、迭代法以及Morris遍歷算法，并通過代碼示例和復雜度分析幫助讀者深入理解。

---

## 一、二叉樹后序遍歷的定義
后序遍歷的順序為：
1. 遍歷左子樹
2. 遍歷右子樹
3. 訪問根節點

示例二叉樹：

 1
/ \

2 3 /
4 5

后序遍歷結果：`[4, 5, 2, 3, 1]`

---

## 二、遞歸實現
遞歸是最直觀的實現方式，直接反映遍歷定義。

### 代碼實現
```python
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def postorderTraversal(root: TreeNode) -> list:
    def dfs(node, res):
        if not node:
            return
        dfs(node.left, res)  # 左子樹
        dfs(node.right, res) # 右子樹
        res.append(node.val) # 根節點
    
    result = []
    dfs(root, result)
    return result

復雜度分析

• 時間復雜度：O(n)，每個節點訪問一次
• 空間復雜度：O(h)，遞歸棧深度（h為樹高）

三、迭代實現

通過顯式棧模擬遞歸過程，避免遞歸的系統開銷。

方法一：雙棧法

def postorderTraversal(root: TreeNode) -> list:
    if not root:
        return []
    
    stack = [root]
    result = []
    
    while stack:
        node = stack.pop()
        result.append(node.val)
        # 注意入棧順序：先左后右 → 出棧順序變為右左
        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)
    
    return result[::-1]  # 反轉得到后序

方法二：標記法

def postorderTraversal(root: TreeNode) -> list:
    stack = [(root, False)]
    result = []
    
    while stack:
        node, visited = stack.pop()
        if not node:
            continue
        if visited:
            result.append(node.val)
        else:
            # 入棧順序與訪問順序相反
            stack.append((node, True))
            stack.append((node.right, False))
            stack.append((node.left, False))
    
    return result

復雜度分析

• 時間復雜度：O(n)
• 空間復雜度：O(h)

四、Morris遍歷算法

無需額外空間的高效算法，通過修改樹結構實現。

實現步驟

1. 建立臨時鏈接
2. 利用線索化二叉樹特性

代碼實現

def postorderTraversal(root: TreeNode) -> list:
    result = []
    dummy = TreeNode(0)
    dummy.left = root
    current = dummy
    
    while current:
        if not current.left:
            current = current.right
        else:
            pre = current.left
            while pre.right and pre.right != current:
                pre = pre.right
            
            if not pre.right:
                pre.right = current  # 建立臨時鏈接
                current = current.left
            else:
                pre.right = None  # 恢復樹結構
                # 記錄左子樹到pre的路徑
                temp = current.left
                nodes = []
                while temp:
                    nodes.append(temp.val)
                    temp = temp.right
                result += nodes[::-1]
                current = current.right
    
    return result

復雜度分析

• 時間復雜度：O(n)
• 空間復雜度：O(1)

五、應用場景

1. 表達式樹求值
2. 內存釋放（先釋放子節點再父節點）
3. 文件系統目錄刪除

六、總結對比

七、練習題

1. 給定二叉樹 [1,null,2,3]，手動計算其后序遍歷
2. 嘗試用非遞歸方法實現N叉樹的后序遍歷
3. LeetCode 145題：二叉樹的后序遍歷

參考文獻

1. 《算法導論》- Thomas H. Cormen
2. LeetCode官方題解
3. GeeksforGeeks二叉樹專題

”`

（全文約1150字）