LeetCode 145. 二叉树的后序遍历

约 5 分钟
文章信息 17 个分类 5 个标签
分类
LeetCode CodeTop 简单 已解决 已掌握 20-50 字节跳动 微软 美团 阿里巴巴 快手 腾讯 猿辅导 百度 拼多多 网易 虾皮
标签
深度优先搜索 树 二叉树 栈 后序遍历
目录

题目描述

✅ 145. 二叉树的后序遍历

image-20230305165334273

题意分析

给定二叉树的根节点，返回它的后序遍历结果。后序的定义是「左子树、右子树、根节点」——对每一棵子树都递归成立，根节点永远是它那棵子树里最后一个被记录的。

约束信号有两个。一是节点数在 [0, 100]、节点值在 [-100, 100]，规模极小，所以本题真正在意的不是效率，而是写法本身对不对。二是进阶明确要求「递归很简单，你可以用迭代实现吗」——这句话把递归降级成热身，面试里问 145 基本就是在问那份迭代写法。

边界情况：根为空时返回空列表；只有一个节点时返回该节点值；链状树（每个节点只有左孩子或只有右孩子）会把递归栈压到 $O(n)$ 深，也是迭代写法必须能正确处理的形状。

解法：根右左遍历后反转结果

核心思路

问题关键：后序是「左、右、根」，根节点只有在两棵子树都处理完后才能输出。直接模拟这个回溯时机需要额外记录上一次访问的节点，迭代条件较复杂。

为什么选镜像前序加反转：后序整体反转后是「根、右、左」。它正好是前序模板交换左右顺序后的结果，因此可以先用栈得到「根、右、左」，最后一次性反转为「左、右、根」。每次从结果头部插入也能得到相同顺序，但数组头插会退化到 $O(n^2)$。

不变量：栈中保存尚未展开的节点；每次弹出后立即记录，并按「先左后右」压栈。因为栈后进先出，右孩子必先于左孩子被访问，所以任意子树产生的序列都是 根 + 右子树镜像前序 + 左子树镜像前序。

正确性：将上述序列整体反转，拼接顺序也随之反转，得到 左子树后序 + 右子树后序 + 根，正是后序定义。每个非空节点只入栈、出栈一次，因此既不会遗漏也不会重复。

这是容易口述和实现的主解法；若面试官明确要求不反转，可改用「栈 + prev 指针」判断右子树是否已经访问。

解题步骤

  1. 若根为空，直接返回空列表；否则将根压栈。
  2. 栈非空时弹出节点并记录其值。
  3. 依次压入非空的左孩子、右孩子。右孩子后入先出，因此访问顺序为「根、右、左」。
  4. 栈清空后反转结果并返回。

口述样例：三节点树 1 的左右孩子为 2、3。弹出 1 后先压 2 再压 3，接着依次弹出 3、2，得到 [1,3,2]；反转后为后序 [2,3,1]。

代码实现

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }

        Deque<TreeNode> stack = new ArrayDeque<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            res.add(node.val);
            if (node.left != null) {
                stack.push(node.left);
            }
            if (node.right != null) {
                stack.push(node.right);
            }
        }

        // 当前顺序是根右左，反转后得到左右根。
        Collections.reverse(res);
        return res;
    }
}

func postorderTraversal(root *TreeNode) []int {
    res := make([]int, 0)
    if root == nil {
        return res
    }

    stack := []*TreeNode{root}
    for len(stack) > 0 {
        node := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        res = append(res, node.Val)
        if node.Left != nil {
            stack = append(stack, node.Left)
        }
        if node.Right != nil {
            stack = append(stack, node.Right)
        }
    }

    // 根右左反转后就是后序的左右根。
    for left, right := 0, len(res)-1; left < right; left, right = left+1, right-1 {
        res[left], res[right] = res[right], res[left]
    }
    return res
}

复杂度分析

  • 时间复杂度：$O(n)$。每个节点入栈、出栈一次，最后反转结果仍是线性操作。
  • 空间复杂度：$O(h)$，h 为树高，最坏为 $O(n)$；返回结果不计入额外空间。

关键点总结

  • 核心等式是「后序 = 反转后的根右左」，不是机械记忆压栈顺序。
  • 为得到「根右左」，栈中必须先压左孩子、再压右孩子。
  • 一次整体反转是 $O(n)$；不要对数组反复头插。
  • 若要求原生后序顺序，使用 prev 记录上次访问节点：右子树为空或已访问时才能输出根。
  • 若进一步要求 $O(1)$ 额外空间，可讨论 Morris 后序，但实现明显更复杂，不应作为默认方案。

易错点总结

  • 沿用前序的「先右后左」压栈：三节点树最终会得到 [3,2,1]，左右顺序颠倒。
  • 忘记反转：返回的是 [1,3,2] 这种「根右左」，不是后序。
  • 把空孩子压栈或空根直接入栈，弹出后访问节点值会产生空指针错误。
  • 使用 res.add(0, value) 代替末尾反转，数组搬移会使总复杂度退化为 $O(n^2)$。
  • 改用 ArrayDeque 后混用 add 和 pop 会变成队尾入、队头出，遍历语义不再是栈。

相似题目

题目 难度 考察点
94. 二叉树的中序遍历 简单 中序无法靠反转得到，迭代必须显式「一路向左压栈再回弹」
144. 二叉树的前序遍历 简单 同一套栈模板的原型，压栈顺序先右后左且无需反转
102. 二叉树的层序遍历 中等 把栈换成队列，并按层切分结果
589. N 叉树的前序遍历 简单 孩子数不定，需倒序压入 children 才能保持从左到右
590. N 叉树的后序遍历 简单 反转法的直接推广，正序压入孩子后整体反转