深入理解后序遍历（Python实现二叉树后序遍历算法详解）

为什么学习后序遍历？

后序遍历在实际开发中有许多应用场景，比如：

• 删除二叉树时，需要先删除子节点再删除父节点；
• 计算目录大小（文件系统本质是一棵树）；
• 表达式求值（如后缀表达式）。

Python实现：递归方式

递归是最直观、最简洁的实现方式。我们首先定义一个简单的二叉树节点类，然后编写后序遍历函数。

class TreeNode:    def __init__(self, val=0, left=None, right=None):        self.val = val        self.left = left        self.right = rightdef postorder_traversal_recursive(root):    """    递归实现后序遍历    :param root: 二叉树根节点    :return: 遍历结果列表    """    result = []        def dfs(node):        if not node:            return        # 先遍历左子树        dfs(node.left)        # 再遍历右子树        dfs(node.right)        # 最后访问根节点        result.append(node.val)        dfs(root)    return result# 示例使用if __name__ == "__main__":    # 构建如下二叉树:    #       1    #      / \    #     2   3    #    / \    #   4   5    root = TreeNode(1)    root.left = TreeNode(2)    root.right = TreeNode(3)    root.left.left = TreeNode(4)    root.left.right = TreeNode(5)        print(postorder_traversal_recursive(root))  # 输出: [4, 5, 2, 3, 1]

Python实现：迭代方式（使用栈）

虽然递归写法简洁，但在处理非常深的树时可能引发栈溢出。因此，掌握非递归（迭代）实现也很重要。后序遍历的迭代实现比前序和中序稍复杂，常用技巧是“逆后序”+反转。

def postorder_traversal_iterative(root):    """    迭代实现后序遍历（使用栈）    :param root: 二叉树根节点    :return: 遍历结果列表    """    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]# 测试同上例print(postorder_traversal_iterative(root))  # 输出: [4, 5, 2, 3, 1]

总结与进阶建议

通过本文，你已经掌握了两种实现后序遍历算法的方法：递归和迭代。对于初学者，建议先熟练掌握递归写法，再挑战迭代版本。理解这些基础的Python数据结构操作，将为你在算法竞赛或面试中打下坚实基础。

记住，后序遍历的核心思想是“子任务完成后再处理当前任务”，这种思维模式在解决很多递归问题时都非常有用。

关键词回顾：

• Python后序遍历
• 二叉树后序遍历
• 后序遍历算法
• Python数据结构