面试题33：二叉搜索树的后序遍历序列

从“最后一个数为什么决定整段分区”开始

先预测：序列7、4、6、5的最后一个数5若作为根，第一个大于5的7意味着右子树从7开始；但随后4又小于5。右子树中不能出现比根小的节点，所以不需要真的造树就能判false。

二叉树后序顺序是左子树、右子树、根，因此任意非空连续子序列的根节点都在末尾。二叉搜索树又要求左侧所有值小于根，右侧所有值大于根。于是“最后一个数字是根节点”同时给出了结构位置和值域分割依据。

题目判断的是“二叉搜索树的后序遍历序列”。作者明确假设所有数字互不相同，所以小于与大于是严格关系，不需要决定重复键落左还是落右。

先找分割点，再完整检查右段

令root等于末尾值。从序列开头扫描，首个大于root的位置i是。i之前的值都未触发大于条件，在互异前提下全部小于root，构成候选左子树。

从i继续扫描到根前，任何值小于root都形成，立即返回false。若没有冲突，顶层满足“左子树小于根，右子树大于根”，但还不能返回true：左右段内部也必须分别能形成二叉搜索树。

只找第一个大值而不检查后续，会错误接受7、4、6、5；只检查当前根而不递归，又可能接受子段内部违反其自身根的序列。两个阶段分别保证当前层分区和所有后代分区。

忠实还原作者递归实现

作者接收可写int数组指针，但函数不修改内容。空指针或长度不正直接false；单元素取根后两次扫描均为空，左右默认true，最终true。

bool VerifySquenceOfBST(int sequence[], int length) {
    if (sequence == nullptr || length <= 0) {
        return false;
    }
 
    const int root = sequence[length - 1];
 
    int i = 0;
    for (; i < length - 1; ++i) {
        if (sequence[i] > root) {
            break;
        }
    }
 
    for (int j = i; j < length - 1; ++j) {
        if (sequence[j] < root) {
            return false;
        }
    }
 
    bool left = true;
    if (i > 0) {
        left = VerifySquenceOfBST(sequence, i);
    }
 
    bool right = true;
    if (i < length - 1) {
        right = VerifySquenceOfBST(
            sequence + i, length - i - 1);
    }
    return left && right;
}

左递归长度是i，覆盖下标0到i减1；右递归从sequence+i开始，长度length减i减1，排除最后的root。i为0表示左子树空，i等于length减1表示右子树空，都不调用长度0递归，因为作者顶层把长度0定义为false。

把左右默认设为true，相当于“空子树在父节点内部合法”；但独立传入空序列仍按作者API返回false。这两个语义不矛盾：递归实现选择不调用空段，外部接口则拒绝没有节点的输入。

正确性证明

对子序列长度归纳。长度1只含根，是合法BST后序。假设所有更短非空序列都能被正确判断。

当前末尾必是根。若从首个大于根的元素开始，右段出现小于根的值，则不存在连续“左、右、根”分区，序列必非法。若当前分区全部满足严格大小关系，那么整段合法当且仅当候选左段和右段各自是BST后序。

算法递归的正是这两个更短连续子段，由归纳假设分别正确。两边都true时，可把其对应BST接到root左右形成一棵BST，后序恰为原序列；任一边false时不存在合法子树。因此递归条件既必要又充分。

这里的递归验证子序列，是指每次确定当前根和左右边界后，把两个更短的连续片段交给同一规则验证；只有左右片段都通过，当前序列才算合法，不能只检查顶层分割。

把这个过程看作构造性证明：算法虽不分配节点，却隐含地给出每棵子树的根与左右范围。

复杂度为何最坏是平方

每层递归要线性扫描当前子段。平衡分割时工作量近似n加两个n/2问题，总时间O(n log n)；单链序列1、2、3、4、5或5、4、3、2、1每次只缩短1，扫描长度之和为n加n减1直到1，最坏O(n²)。

递归栈平衡时O(log n)，单链时O(n)，极长输入可能调用栈溢出。原书方案突出后序分区直觉；若生产数据很大，可用单调栈在线性时间验证。

返回布尔值不创建树，除递归栈外控制空间如上。使用数组指针和长度不会复制子序列；若每次slice新vector，会额外产生大量复制与分配，最坏时间和内存都恶化。

O(n)单调栈替代法

逆向读取后序得到根、右、左顺序。维护一个递减关系的节点栈和upper。读到更小值时不断弹出，表示从右链回退到祖先左侧，并把最后弹出的祖先设为新上界；若后续值大于上界，就跨回了已关闭的右侧区域。

#include <limits>
#include <stack>
#include <vector>
 
bool verifyPostorderLinear(const std::vector<int>& postorder) {
    if (postorder.empty()) {
        return false;  // Match the author's external policy.
    }
 
    long long upper = std::numeric_limits<long long>::max();
    std::stack<int> ancestors;
 
    for (auto it = postorder.rbegin();
         it != postorder.rend(); ++it) {
        const int value = *it;
        if (value > upper) {
            return false;
        }
 
        while (!ancestors.empty() &&
               value < ancestors.top()) {
            upper = ancestors.top();
            ancestors.pop();
        }
        ancestors.push(value);
    }
    return true;
}

每个值入栈一次、出栈至多一次，时间O(n)、空间O(n)。这段同样假设值互异；若重复允许在右侧或左侧，比较符号和上界等号政策必须成套修改。不要只改一个小于号。

递归版更直接对应作者源码和证明；单调栈版更适合大输入，但状态含义较难在面试中首次推导。章节应先掌握分区递归，再用上界理解优化。

作者八组测试覆盖什么

Test1序列4、8、6、12、16、14、10对应三层完整BST；Test2的4、6、7、5对应根5、左4、右7且7的左孩子6。两者验证左右子树同时存在及内部递归。

Test3递增1到5对应全左链，Test4递减5到1对应全右链，锁定一侧为空和O(n)递归深度。Test5单值5返回true。

Test6的7、4、6、5在根5右段发现4；Test7的4、6、12、8、16、14、10在根10右段发现8，都是跨位置冲突。Test8传nullptr、0，返回false。源码总计八组。

#include <cassert>
#include <vector>
 
void testPostorder() {
    assert(verifyPostorderLinear(
        {4, 8, 6, 12, 16, 14, 10}));
    assert(verifyPostorderLinear({4, 6, 7, 5}));
    assert(verifyPostorderLinear({1, 2, 3, 4, 5}));
    assert(verifyPostorderLinear({5, 4, 3, 2, 1}));
    assert(verifyPostorderLinear({5}));
    assert(!verifyPostorderLinear({7, 4, 6, 5}));
    assert(!verifyPostorderLinear(
        {4, 6, 12, 8, 16, 14, 10}));
    assert(!verifyPostorderLinear({}));
}

还应让递归版与单调栈版对随机互异数组交叉校验。生成合法样本时先构造随机BST再取后序；非法样本不能只随机交换一次并假设必非法，因为交换后仍可能对应另一棵BST，必须以参考验证器给出标签。

重复值、空序列与接口契约

作者题干说明所有数字互不相同。源码寻找左段时遇到大于root才停止，右段只拒绝小于root，因此等于root的值会落入右段并可能被接受；这不是重复键策略，而是前提保证等号永不出现。

若业务允许重复，必须先定义BST不变量：重复全部放左、全部放右、节点计数聚合，或禁止。分割扫描、右段检查、单调栈上界与测试都要按同一政策修改。仅因为当前源码偶然接受某些重复序列，不能推断作者支持重复。

现代平台常把空序列看作空树的合法后序并返回true；作者Test8明确期待false。可把外部入口的空输入政策与内部空子树基例分开，让API文档和测试一致。

输入指针还要求至少可读length个int。负长度被拒绝，但过大错误长度仍会越界；vector或span能携带真实范围。函数只读数据，应改为const int指针表达契约。

工程边界与诊断

若只返回false，调用方不知道在哪一层失败。可以返回当前子序列范围、根值、分割点和右段首个小值；Test7会报告顶层root10、右段起点12、冲突值8。诊断不改变验证逻辑，却显著提高可解释性。

一份稳定诊断应使用原数组下标，而不是递归子指针的局部下标。例如记录range=[begin,end)、rootIndex=end减1、splitIndex与conflictIndex；递归右段时只更新begin为split，end为旧rootIndex。这样Test1的顶层范围是[0,7)，左段[0,3)，右段[3,6)，日志可直接对应原序列。若复制slice后只报告局部位置，调用方还要累加多层偏移，容易在空左段或空右段处产生一位误差。

对成功序列也可输出一棵“范围证明树”：每个节点保存根值和左右区间，不必分配真实BinaryTreeNode。它既能展示递归结构，也能验证所有区间互不重叠且覆盖除各层根外的元素；需要真正重建BST时，再按同样范围递归创建节点。

递归实现可先验证右段再递归，像作者一样在顶层冲突处尽早返回。左右递归使用逻辑与短路，左失败后可不验证右；若需要收集全部错误，则要继续两侧并聚合诊断，时间仍受最坏平方界。

并发修改输入会使不同递归层看到不同序列，必须使用不可变快照或外部读锁。对浮点值，NaN破坏严格全序，不应直接复用比较；提供全序比较器或拒绝非有限数。

本章练习

概念说明

递归验证子序列。

本章回顾

1. 后序序列最后一个数字是当前子树根节点。
2. 从开头到首个大于根的值是候选左段，其后是候选右段。
3. 右段出现小于根的值，序列立即非法。
4. 当前分区通过后仍要递归验证左右子序列。
5. 作者跳过空子段，但外部空输入返回false，单元素返回true。
6. 递归版平均依形状而定，单链最坏O(n²)、栈深O(n)。
7. 逆序单调栈以祖先上界实现O(n)验证。
8. 作者假设值互异，重复键策略不能从比较符号偶然行为推断。

名词解释