如何返回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字）