LC145 二叉树的后序遍历 · 逐题动画 · RuntimeScope

RuntimeScope/算法实验台/56 天打卡/141 题/LC145

题型地图 56天全屏 141题

当前：LC145 · 二叉树的后序遍历 · 首次出现于 Day 18 · 路径：顶栏「56天打卡」→ 点击 LC 题号 → 逐题动画

← LC144 LC146 →

65 / 141回到 Day 18 卡片 141 题索引

LC145 · 后序遍历 · 工程执行实验室

左右完才记录根

后序遍历 = 左右子树都处理完之后，才把当前节点加入结果。用 current、ans、递归栈/显式栈把执行过程讲清楚，并分开理解递归版与迭代逆序法。

示例树（层序）

[3, 9, 20, null, null, 15, 7]

输出：[9, 15, 7, 20, 3]

核心心智模型

后序遍历 = 左右子树都处理完之后，才把当前节点加入结果。

· 访问顺序口诀：左子树 → 右子树 → 根（左-右-根）。
· 与前序/中序最大区别：根节点不能一进入就输出，必须等左右都走完。
· 递归返回后自然保证顺序：dfs(Left) 和 dfs(Right) 都 return 了，才 append。

不变量

ans 中保存的是左右子树均已处理完的节点；call stack 中保存的是已进入但尚未 append 的节点。

递归版 vs 迭代版（分开理解）

递归版

先 dfs(Left)、再 dfs(Right)，左右都 return 后才 append。暂停状态由系统调用栈保存。

迭代版

用栈做根-右-左遍历收集到 rev，最后 reverse 得到后序。不能简单对称前序压栈顺序。

1/17 · Step 1 · 题目与输入

7 阶段：

帧 0Step 1 · 题目与输入阶段 1

题目与输入：示例树与后序目标输出

给定二叉树：根 3，左孩子 9，右子树 20-15-7。后序遍历的目标输出是 [9, 15, 7, 20, 3]——整棵左子树、整棵右子树都处理完后，根 3 才最后出现。

为什么

先看清树结构和期望序列，后面每一步都能对照「为什么根在最后」。

状态表 · current / ans / 栈

current	ans	stack（显式，栈顶在右）	下一步	动作
current = 3（节点 1）	[]	[]	即将学习后序规则	读题

目标输出 [9,15,7,20,3]

current 高亮·等待左右·已记录·在栈中

Go · 递归版（左右完才 append）

1func postorderTraversal(root *TreeNode) []int {
2    res := []int{}
3 
4    var dfs func(node *TreeNode)
5    dfs = func(node *TreeNode) {
6        if node == nil {
7            return
8        }
9 
10        dfs(node.Left)
11        dfs(node.Right)
12        res = append(res, node.Val)
13    }
14 
15    dfs(root)
16    return res
17}

展开迭代版（对比 reverse 技巧）

func postorderTraversal(root *TreeNode) []int {
    if root == nil {
        return nil
    }
    rev := []int{}
    stack := []*TreeNode{root}
    for len(stack) > 0 {
        n := len(stack)
        node := stack[n-1]
        stack = stack[:n-1]

        rev = append(rev, node.Val)

        if node.Left != nil {
            stack = append(stack, node.Left)
        }
        if node.Right != nil {
            stack = append(stack, node.Right)
        }
    }
    // reverse rev → 后序
    for i, j := 0, len(rev)-1; i < j; i, j = i+1, j-1 {
        rev[i], rev[j] = rev[j], rev[i]
    }
    return rev
}

复杂度

时间: O(n)
空间: O(h)

每个节点访问一次，共 n 个节点。

h 为树高；递归用系统调用栈，迭代用显式 stack，最坏退化链表时 O(n)。

Morris 后序遍历可做到额外空间 O(1)，但本页主讲递归/栈解法。

面试回答

后序遍历按照左-右-根的顺序访问。递归写法是先 dfs(Left)、再 dfs(Right)，最后 append 当前节点；与前序/中序的差别在于 append 时机——必须等左右子树都处理完。迭代可用「根-右-左」遍历再 reverse 得到后序。每个节点访问一次，时间 O(n)，空间 O(h)，最坏 O(n)，不是 O(1)。

常见误区

误区 1：一进节点就 append

这是前序写法。后序必须等 dfs(Left) 和 dfs(Right) 都返回后，才 append 当前节点。

误区 2：把前序栈法直接对称

后序迭代不能简单「先压左再压右」。常用技巧是根-右-左遍历后 reverse，或双栈/lastVisited 标记。

误区 3：误以为空间复杂度是 O(1)

递归/显式栈版本空间是 O(h)，最坏 O(n)，不是 O(1)。

误区 4：忘记处理 root == nil

空树应直接返回空切片，否则会对空指针解引用。