LeetCode 剑指 Offer 33. 二叉搜索树的后序遍历序列

约 5 分钟
文章信息 15 个分类 7 个标签
分类
LeetCode CodeTop 中等 未解决 10-20 字节跳动 微软 美团 滴滴 拼多多 网易 小米 虾皮 剑指 Offer 剑指 Offer（第 2 版）
标签
数组 树 二叉树 栈 递归 二叉搜索树 单调栈
目录

题目描述

✅ 剑指 Offer 33. 二叉搜索树的后序遍历序列

image-20241107210651864

image-20241107210641598

题意分析

给一个互不相同的整数数组，判断它能否是某棵二叉搜索树的后序遍历结果。注意问的是「存在性」而不是「还原出这棵树」——不需要真的把树建出来，只要证明存在一棵合法的 BST 即可。

约束信号有两条。其一，元素互不相同，这让 BST 里「左子树严格小于根、右子树严格大于根」的判定不用考虑相等的歧义。其二，后序遍历的结构极其死板：左子树的全部节点、右子树的全部节点、根节点，三段严格按这个顺序排列，中间没有任何交叉。加上 BST 的大小约束，这棵树的形状其实被序列唯一确定，所以「能否」实际上等价于「按唯一还原方式检查是否处处合法」。

边界情况：空数组和单元素数组都合法，分别对应空树和只有根的树；序列长度为 2 时无论大小关系如何都合法，因为那个非根元素既可以挂在左边也可以挂在右边。

解法：反向后序 + 上下界校验

核心思路

二叉搜索树的后序遍历顺序是「左子树、右子树、根」。从数组末尾反向读取，顺序就变成「根、右子树、左子树」，与按上下界验证 BST 的过程完全一致。

维护指针 index 从右向左扫描，并让递归函数接收当前子树允许的开区间 (lower, upper)：

  • 当前值不在区间内，说明当前子树为空；不消费该值，把它留给祖先的另一棵子树。
  • 当前值在区间内，它就是当前子树的根；消费后先验证范围 (value, upper) 的右子树，再验证 (lower, value) 的左子树。

不变量：每次递归开始时，index 指向尚未归属的最右元素，区间表示它若属于当前子树必须满足的全部祖先约束。

正确性：算法每消费一个值，都把它放在满足 BST 上下界的位置，并按「根、右、左」读取，因此若最终所有值都被消费，就构造出了一棵以后序顺序匹配原数组的 BST。反之，合法 BST 的反向后序必然按相同区间依次进入根、右、左，算法不会拒绝其中任何元素。

解题步骤

  1. 将 index 初始化为数组最后一个下标。
  2. 从无穷小到无穷大的开区间开始递归；Java 用 long 边界，避免 int 极值与哨兵冲突。
  3. 若元素已用完，或当前值不在区间内，直接返回且不移动指针。
  4. 当前值在区间内时先保存为根，再执行 index--。
  5. 先递归右子树 (value, upper)，再递归左子树 (lower, value)。
  6. 最终只有 index == -1 才合法；仍有元素说明它无法归入任何允许区间。

例如 [1, 3, 2, 6, 5] 反向为 5, 6, 2, 3, 1：先确定根 5，6 落入右区间；2 落入左区间，随后 3 和 1 分别落入 2 的右、左区间，所有元素恰好被消费。非法序列 [1, 6, 3, 2, 5] 会留下无法放入当前上下界的 6。

代码实现

class Solution {
    private int index;

    public boolean verifyPostorder(int[] postorder) {
        index = postorder.length - 1;
        consume(postorder, Long.MIN_VALUE, Long.MAX_VALUE);
        return index == -1;
    }

    private void consume(int[] postorder, long lower, long upper) {
        if (index < 0) {
            return;
        }

        long value = postorder[index];
        if (value <= lower || value >= upper) {
            return;
        }

        index--;
        consume(postorder, value, upper);
        consume(postorder, lower, value);
    }
}

func verifyPostorder(postorder []int) bool {
    index := len(postorder) - 1

    var consume func(int64, int64)
    consume = func(lower, upper int64) {
        if index < 0 {
            return
        }

        value := int64(postorder[index])
        if value <= lower || value >= upper {
            return
        }

        index--
        consume(value, upper)
        consume(lower, value)
    }

    consume(-1<<63, 1<<63-1)
    return index == -1
}

复杂度分析

  • 时间复杂度：$O(n)$。每个元素只会被消费一次；空子树只产生常数次边界判断。
  • 空间复杂度：$O(h)$。h 是对应 BST 的高度；平衡树为 $O(\log n)$，链状树最坏为 $O(n)$。

关键点总结

  • 反向后序是「根、右、左」，所以递归顺序必须先右后左。
  • 上下界携带了所有祖先约束，只与当前根比较是不够的。
  • 越界表示「当前子树为空」，不是立即判错，因此不能移动指针。
  • 是否非法由最终 index == -1 统一判断。
  • 使用开区间对应题目中节点值互不相同的条件。
  • 面试时先说明朴素分治最坏 $O(n^2)$，再给出反向扫描的 $O(n)$ 优化，推导会更完整。

易错点总结

  • 先递归左子树：反向扫描先遇到右子树元素，会把合法序列误判为非法。
  • 越界时返回失败或移动指针：越界元素可能属于祖先的另一侧，必须原样留给上层。
  • 只检查与直接父节点的大小关系：会遗漏更高层祖先施加的范围限制。
  • 省略最终指针检查：无法归属的元素可能被当作空子树跳过，导致非法序列返回 true。
  • 用 int 极值充当开区间边界：输入恰好包含 Integer.MIN_VALUE 或 Integer.MAX_VALUE 时会被误判。
  • 忽略重复值规则：本题保证值互不相同；若允许重复，必须先约定重复值属于哪一侧并相应调整边界。

相似题目

题目 难度 考察点
98. 验证二叉搜索树 中等 树上递归传递上下界
105. 从前序与中序遍历序列构造二叉树 中等 前序定根加中序定分割
106. 从中序与后序遍历序列构造二叉树 中等 后序末元素定根的建树
255. 验证二叉搜索树的前序遍历序列 中等 前序序列的单调栈校验
331. 验证二叉树的前序序列化 中等 用槽位计数校验序列合法性
449. 序列化和反序列化二叉搜索树 中等 借助 BST 性质压缩序列化
1008. 前序遍历构造二叉搜索树 中等 上下界法从前序还原 BST