CS-Notes 剑指 Offer：如何判断一个整数数组是二叉搜索树的后序遍历序列

本文基于 CS-Notes 仓库中 33. 二叉搜索树的后序遍历序列 这道剑指 Offer 经典题目展开：给定一个互不重复的整数数组，判断它是否可能是一棵二叉搜索树（BST）的后序遍历结果。文章完整继承原题的题面与参考实现，并逐行剖析其"切分 + 递归"的判断逻辑、给出两个完整的手工推演例子与复杂度分析，同时结合同仓库中几道 BST 相关题解，帮助读者吃透"后序结构 + BST 有序性"这一核心考点。

题目描述

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。假设输入的数组的任意两个数字都互不相同。

例如，后序遍历序列 1, 3, 2 所对应的二叉搜索树如下（左子树为 1，右子树为 3，根为 2）：

    2
   / \
  1   3

其对应的后序遍历正是 1, 3, 2：先遍历左子树 1，再遍历右子树 3，最后是根 2。

题面来源见 剑指 Offer 题解目录，该题在目录中归属于"树"这一分类。

核心思路：后序结构 + BST 有序性

要判断一个序列能否还原成 BST 的后序遍历，需要同时利用两个性质：

1. 后序遍历的结构：序列形如 左子树序列 | 右子树序列 | 根。也就是说，数组最后一个元素一定是当前子树的根。
2. BST 的有序性：左子树中的所有值都小于根，右子树中的所有值都大于根（题目保证任意两个数字互不相同，因此不存在等于根的情况）。

结合这两点，判断过程就变成对区间 [first, last] 的递归：

• 取 sequence[last] 作为 rootVal（当前子树的根）；
• 从 first 开始向右扫描，第一个大于 rootVal 的元素就是右子树序列的起点 cutIndex；[first, cutIndex - 1] 是左子树，[cutIndex, last - 1] 是右子树；
• 关键校验：右子树序列中一旦出现小于 rootVal 的元素，说明该元素既不在合法的左子树区间内、值又不满足右子树要求，序列非法，直接返回 false；
• 递归校验左右两个子区间，两者都合法则当前区间合法。

这个"按根值把序列切成左右两段、再检查右段下界"的过程，正是仓库参考代码要做的事情。

参考实现逐行剖析

下面是 33. 二叉搜索树的后序遍历序列 中给出的 Java 参考代码（完整保留原实现）：

public boolean VerifySquenceOfBST(int[] sequence) {
    if (sequence == null || sequence.length == 0)
        return false;
    return verify(sequence, 0, sequence.length - 1);
}

private boolean verify(int[] sequence, int first, int last) {
    if (last - first <= 1)
        return true;
    int rootVal = sequence[last];
    int cutIndex = first;
    while (cutIndex < last && sequence[cutIndex] <= rootVal)
        cutIndex++;
    for (int i = cutIndex; i < last; i++)
        if (sequence[i] < rootVal)
            return false;
    return verify(sequence, first, cutIndex - 1) && verify(sequence, cutIndex, last - 1);
}

逐段解释：

代码位置	作用说明
VerifySquenceOfBST 入口的空值/空数组判断	仓库实现将 null 或长度为 0 的输入约定为返回 false，即空序列不视为合法的后序序列。这是该题实现中的一个边界约定，面试时需与题目要求保持一致
if (last - first <= 1) return true;	递归基：区间长度小于等于 1 时，单个元素（或空区间）必然可以构成一棵合法的 BST 子树
int rootVal = sequence[last];	后序遍历的最后一个元素一定是当前子树的根
while (cutIndex < last && sequence[cutIndex] <= rootVal) cutIndex++;	从左向右扫描，收集所有小于等于根值的元素作为左子树。题目保证元素互不相同，<= 实际等价于 <；扫描结束后 cutIndex 恰好指向右子树序列的第一个元素
for (int i = cutIndex; i < last; i++) if (sequence[i] < rootVal) return false;	校验右子树下界：右子树区间内的任何元素都必须大于根，一旦发现小于根的元素即判非法。这一步是本题最容易被忽略、也是区分解法正确性的核心检查
末尾的双重递归	左子树区间为 [first, cutIndex - 1]，右子树区间为 [cutIndex, last - 1]。注意当子区间为空时（如 cutIndex == first，first > cutIndex - 1），会落入递归基 last - first <= 1 直接返回 true，因此无需额外判空

两个完整推演例子

例 1：合法序列 [1, 3, 2, 5, 4, 6, 8]

该序列对应这棵 BST（2 的右孩子是 4，2 的左孩子是 1，4 的右孩子是 5，6 是 4 的右子树中的兄弟节点……具体结构为）：

        8
       / \
      4   6
     / \
    2   5
   / \
  1   3

按算法执行：

1. 根 8：1, 3, 2, 5, 4, 6 全部小于 8，右子树为空，右段校验通过，递归 [0, 5]；
2. 根 6：1, 3, 2, 5, 4 全部小于 6，右子树为空，递归 [0, 4]；
3. 根 4：扫描到 5 > 4，cutIndex 停在 5 处，切出左段 [1, 3, 2]、右段 [5]；右段 5 > 4 校验通过；
4. 递归左段，根 2：切出左段 [1]、右段 [3]，3 > 2 校验通过；
5. 两个叶子区间都落入递归基返回 true。

最终返回 true。

例 2：非法序列 [7, 4, 6, 5]

1. 根 5：扫描 7 > 5，第一个元素就不满足 <= rootVal，故 cutIndex 停在起点，左子树为空，右段为 [7, 4, 6]；
2. 右段下界校验：遍历到 4 时发现 4 < 5，右子树中出现了小于根的元素，立即返回 false。

直觉上，4 想要成为 5 的左子树节点，但它却出现在右子树区间的位置，矛盾成立，序列非法。这个例子恰好展示了"切分 + 右段校验"两步缺一不可：只按根切分而不做下界检查，会漏掉大量非法序列。

复杂度分析

• 时间复杂度：最坏情况下树退化为单链（例如严格递增或严格递减的序列），每一层递归都要扫描一个线性区段，总代价为 O(n²)；平均情况下各层扫描量按树高衰减，远优于此上界；
• 空间复杂度：O(n) 的递归调用栈，最坏为 O(n)；
• 原地性：整个判断过程只读不写，不需要额外数组，适合直接嵌入面试白板实现。

与仓库中相关题解的呼应

这道题的本质是"用遍历序列反推 BST 的结构约束"，与 剑指 Offer 题解 目录中"树"分类下的几道题形成了完整的方法论链条：

• 7. 重建二叉树：正向操作——由前序 + 中序确定根、切分中序区间递归建树。本题是它的"逆问题"：不给前序，只给后序，要求校验切分后的区间是否自洽；两道题共享"根值定位 → 切分区间 → 递归"的骨架；
• 36. 二叉搜索树与双向链表 与 54. 二叉查找树的第 K 个结点：这两道题都直接依赖"BST 中序遍历有序"这一性质。理解中序有序性，是理解本题"左段必全小于根、右段必全大于根"这两个校验条件的前提；
• Leetcode 题解 - 树 中的前中后序遍历章节（含非递归版后序遍历实现）可以补充遍历本身的实现细节，为本题的序列结构分析提供基础。

面试与自查要点

1. 边界约定：仓库实现将 null 与空数组统一返回 false。若题目明确要求"空序列视为合法"，只需调整入口判断，递归主体不受影响；
2. <= 与 <：题目保证元素互不相同，两种写法等价；若放宽为允许重复，则需重新设计等于根值的元素归属，不能简单沿用本实现；
3. 最容易丢分的点：只做"按根切分左右"而漏掉右子树下界检查，会让形如 [7, 4, 6, 5] 的序列被误判为合法；
4. 递归区间的开闭：左子树区间 [first, cutIndex - 1] 可能为空（first > cutIndex - 1），此时必须依赖递归基 last - first <= 1 兜底，代码中正是这样处理的。

按上述结构实现并推演完两个例子后，这道题的判定逻辑——"末位为根、左段小于根、右段大于根、递归收敛"——就可以形成肌肉记忆，直接迁移到所有"遍历序列 ↔ BST 结构"互推类的题目上。