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

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

题目描述

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

image-20261001230752558

image-20261001230752602

题意分析

数组中的值互不相同，要判断是否存在一棵二叉搜索树，其后序遍历恰好等于这个数组。后序顺序是“左子树、右子树、根”，倒着读取就变成“根、右子树、左子树”，可以一边读取根，一边检查后续值能否放入它的子树，无需真正建树。

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

核心思路

[!blue]

用共享下标 index 指向尚未处理的最右侧元素。consume(lower, upper) 尝试读取一棵所有节点都位于开区间 (lower, upper) 内的子树；上下界不仅来自父节点，也保留了更高层祖先的限制。

如果当前值 value 在范围内，它就是这棵子树的根，移动 index 后，先读取右子树 (value, upper)，再读取左子树 (lower, value)。这样右侧所有后代都大于根，左侧所有后代都小于根，同时都满足原有祖先约束。

如果当前值越界，则当前子树不能以它为根。由于反向遍历首先出现的必须是根，此时只能把当前子树视为空并返回；不能跳过这个值，因为它可能是祖先另一侧子树的根。上层随后会用其他范围继续尝试同一个元素。

对合法序列，根、右、左的读取顺序和大小范围都会匹配，所有元素恰好被消费。反过来，如果全部元素都能按这些范围和顺序消费，就等价于构造出了一棵满足全部大小约束的 BST；如果最终仍有元素剩余，它们无法接入已确定的遍历顺序，序列才应判为非法。

解题步骤

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

空数组一开始就有 index == -1，对应空树，返回 true；单个元素被作为根消费后也会返回 true。每次继续向下递归都会先消费一个元素，因此递归一定结束。

代码实现

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(n)$。
  • 空间复杂度：$O(h)$。h 是递归处理的完整或部分子树的最大深度，调用栈最坏为 $O(n)$；空数组占常数空间。

关键点总结

[!green]

  • 反向后序是「根、右、左」，所以递归顺序必须先右后左。
  • 上下界携带了所有祖先约束，只与当前根比较是不够的。
  • 局部越界只关闭当前子树；是否整体非法，要看最终是否还有未消费元素。
  • 子树只由范围和共享下标表示，验证过程不需要分割数组或分配树节点。

易错点总结

[!yellow]

  • 先递归左子树：反向扫描先遇到右子树元素，会把合法序列误判为非法。
  • 越界时返回失败或移动指针：越界元素可能属于祖先的另一侧，必须原样留给上层。
  • 只检查与直接父节点的大小关系：会遗漏更高层祖先施加的范围限制。
  • 省略最终指针检查：无法归属的元素可能被当作空子树跳过，导致非法序列返回 true。
  • 用 int 极值充当开区间边界：输入恰好包含 Integer.MIN_VALUE 或 Integer.MAX_VALUE 时会被误判。
  • 把开区间改成闭区间：题目要求节点值互异，左右子树与根之间应使用严格大小关系。

相似题目

题目 难度 关联与区别
255. 验证二叉搜索树的前序遍历序列 中等 同样验证BST遍历序列，原题是前序，本题逆向看后序时处理的是根、右、左，边界方向不同。
98. 验证二叉搜索树 中等 BST全局大小约束相同，本题输入仅有遍历值序列，需从序列分区或栈状态验证。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2025/97280527
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！