后序遍历：递归+非递归实现

基本概念

后序遍历（Postorder Traversal） 是二叉树深度优先遍历（DFS）的一种。其访问顺序为：左子树 → 右子树 → 根结点。

  • 后序遍历常用于需要先处理子结点再处理父结点的场景（如删除树、计算表达式树的值）。
  • 递归实现简单，非递归实现相对复杂，需要借助双栈或标记法来记录结点是否已访问过右子树。

算法步骤

  1. 递归版：
    • 若当前结点为空，直接返回。
    • 递归遍历左子树。
    • 递归遍历右子树。
    • 访问当前结点（如记录值）。
  2. 非递归版（双栈法）：
    • 利用两个栈 s1 和 s2。
    • 将根结点压入 s1。
    • 循环弹出 s1 栈顶结点，将其压入 s2，然后将其左孩子和右孩子依次压入 s1（先左后右，则弹出时顺序不影响）。
    • 最终 s2 的出栈顺序即为后序遍历顺序（根在最后）。
  3. 非递归版（单栈+标记法）：
    • 使用一个栈，每个元素为 (node, visited)，visited 表示右子树是否已处理。
    • 初始压入 (root, False)。
    • 循环处理：
      • 弹出栈顶。
      • 若结点为空则跳过。
      • 若 visited 为 True，则访问该结点。
      • 否则，重新压入 (node, True)，然后先压右孩子 (node.right, False)，再压左孩子 (node.left, False)（确保左右子树先被处理）。

内部实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
from typing import List, Optional
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
# 递归实现
def postorderTraversal_recursive(root: Optional[TreeNode]) -> List[int]:
    res = []
    
    def postorder(node):
        if not node:
            return
        postorder(node.left)      # 左
        postorder(node.right)     # 右
        res.append(node.val)      # 根
    
    postorder(root)
    return res
# 非递归实现（双栈法）
def postorderTraversal_twoStacks(root: Optional[TreeNode]) -> List[int]:
    if not root:
        return []
    s1 = [root]
    s2 = []
    while s1:
        node = s1.pop()
        s2.append(node)
        # 先左后右压入s1，这样s2的顺序是根→右→左，弹出s2即为左→右→根
        if node.left:
            s1.append(node.left)
        if node.right:
            s1.append(node.right)
    res = []
    while s2:
        res.append(s2.pop().val)
    return res
# 非递归实现（单栈+标记法，更直观）
def postorderTraversal_singleStack(root: Optional[TreeNode]) -> List[int]:
    if not root:
        return []
    res = []
    stack = [(root, False)]  # (node, visited_right)
    while stack:
        node, visited = stack.pop()
        if not node:
            continue
        if visited:
            res.append(node.val)
        else:
            # 顺序：先压根（标记为已访问），再压右，再压左
            stack.append((node, True))
            stack.append((node.right, False))
            stack.append((node.left, False))
    return res

复杂度分析

版本 时间复杂度 空间复杂度 说明
递归 O(n) O(h) h 为树高，最坏 O(n)（斜树），平均 O(log n)
双栈法 O(n) O(n) 两个栈共存储 O(n) 结点
单栈标记法 O(n) O(h) 最坏 O(n)（斜树），平均 O(log n)
  • 时间复杂度：每个结点访问一次，O(n)。
  • 空间复杂度：递归和单栈标记法依赖栈深度；双栈法需要额外的输出栈，空间 O(n)。

应用场景

  • 删除树：必须先删除子结点再删除父结点，后序遍历天然支持。
  • 表达式树求值（后缀表达式）：后序遍历可直接计算表达式的值（左右子树值计算完后，再根据根运算符计算）。
  • 目录树大小统计：先计算子目录大小，再累加到父目录。
  • 计算树的高度：后序遍历可以获取左右子树的高度，然后取最大值加一。
  • 判断平衡二叉树：后序遍历同时返回高度和是否平衡。
  • 真实系统：
    • 文件系统删除（rm -rf 递归删除目录时，先删子文件再删目录）。
    • 依赖解析（如构建工具中的依赖图，先处理依赖再处理当前节点）。
    • 内存垃圾回收中的引用计数（对象不再被引用时，先释放成员，再释放自身）。

相关链接