2022·41 顺序存储判 BST：从中序数组到一个 prev

本文属于「从暴力解到最优解」专题。套路照旧：先把暴力解写对 → 按判分口径估分 → 找浪费 → 升级成最优解。

题目

已知非空二叉树 T 的结点值均为正整数，采用顺序存储方式保存，数据结构定义如下：

typedef struct {                    // MAX_SIZE 为已定义常量
    Elemtype SqBiTNode[MAX_SIZE];   // 保存二叉树结点值的数组
    int      ElemNum;               // 实际占用的数组元素个数
} SqBiTree;

T 中不存在的结点在数组 SqBiTNode 中用 −1 表示。题面给了两棵示例树：T₁ 满足 BST 定义、T₂ 不满足，对应的顺序存储（下标从 0 起，父结点 i 的左孩子在 2i+1、右孩子在 2i+2）：

数组	内容（依次）	ElemNum
`T₁.SqBiTNode`	`[40, 25, 60, -1, 30, -1, 80, -1, -1, 27]`	10
`T₂.SqBiTNode`	`[40, 50, 60, -1, 30, -1, -1, -1, -1, -1, 35]`	11

请设计一个尽可能高效的算法，判定一棵采用这种方式存储的二叉树是否为二叉搜索树，若是则返回 true，否则返回 false。要求：

(1) 给出算法的基本设计思想。 (2) 根据设计思想，采用 C 或 C++ 语言描述算法，关键之处给出注释。

总分 8 分。本题只有两问，没有单独的复杂度问，题面的「尽可能高效」照样是悬在头顶的要求。

第一步：把暴力解写对

写任何解之前，先过这道题真正的门槛——顺序存储怎么遍历。链式二叉树的中序遍历人人会背，这里没有 next 指针，父子关系全靠下标公式现场推：下标 i 的左孩子在 2i+1、右孩子在 2i+2。空子树有两种表示：下标越界（i ≥ ElemNum），或者该位置的值是 −1（题面约定）。两个条件缺一不可。

门槛过了，判定本身有一个经典等价刻画：BST 当且仅当中序遍历序列严格递增。于是最自然的写法浮出水面：中序遍历一遍，把值按访问顺序收进数组，再扫一遍检查是否严格递增：

static int seq[MAX_SIZE];   // 收集中序序列
static int cnt;

static void inorderCollect(SqBiTree T, int i) {
    if (i >= T.ElemNum || T.SqBiTNode[i] == -1) return;  // 越界或 -1 都是空子树
    inorderCollect(T, 2*i + 1);        // 左子树
    seq[cnt++] = T.SqBiTNode[i];       // 访问：值存入序列
    inorderCollect(T, 2*i + 2);        // 右子树
}

int isBST(SqBiTree T) {
    cnt = 0;
    inorderCollect(T, 0);              // 从根（下标 0）开始
    for (int i = 1; i < cnt; i++)      // 相邻比较：必须严格递增
        if (seq[i] <= seq[i - 1]) return 0;
    return 1;
}

拿 T₂ 验证：中序访问顺序是 50, 30, 35, 40, 60（根 40 的左孩子是 50，50 的右孩子是 30，30 的右孩子是 35），检查时发现 30 ≤ 50，返回 false ✓。T₁ 的中序是 25, 27, 30, 40, 60, 80，严格递增，返回 true ✓。

复杂度：每个数组位置至多访问一次，加一遍序列检查，时间 $O (n)$ ；辅助空间是一条长度可达 n 的序列数组， $O (n)$ ，另有 $O (h)$ 的递归栈。

它值多少分

按正确性/最优性两个维度（详见总纲）：

正确性：这道题设计思想的两根支柱——「BST ⟺ 中序严格递增」的等价刻画、顺序存储的下标公式与两种空子树判定——暴力解全都立住了，代码写对就拿正确性维度的主体分。
最优性：这份暴力解时间已经是 $O (n)$ ，在专题里算离最优解最近的一次；与标准答案的差距只剩那条 $O (n)$ 的序列数组——标准答案连它都不存，只留一个变量。

分差是四篇里最小的，但升级成本也最低：省掉数组几乎不用改代码结构。既然零成本，就把它做掉。

暴力解的浪费在哪

用总纲的三个问题审一遍：

有没有存下用不上的东西？——有。检查阶段干的事只有相邻比较：seq[i] 只和左右邻居各比一次。也就是说，访问到任何一个结点时，唯一需要的历史信息就是「上一个被访问的值」——一个数。暴力解为了这一个数，把整条序列全存了下来。

**有没有干多余的活？——有一处。**先遍历完、再检查，意味着即使第 2 个被访问的结点就已经暴露了违反（T₂ 正是如此：50 之后紧跟 30），暴力解也要把整棵树走完、整条序列存完，才在检查循环里发现问题。

浪费的本质：只需要「上一个值」，却保存了「所有值」；违反在途中就能发现，却拖到终点才判。

智慧化改造：把数组换成一个 prev

对策直接从浪费反推：遍历的时候维护一个变量 prev（上一个被中序访问的值），每访问一个结点，当场和 prev 比——cur ≤ prev 立刻判负；否则更新 prev 继续。序列数组消失，检查循环消失，发现违反当场收工。

typedef struct {
    int SqBiTNode[MAX_SIZE];
    int ElemNum;
} SqBiTree;

static int prev_val;        // 上一次中序访问到的值，全局便于递归
static int g_ok;            // 当前判定结果

static void inorderCheck(SqBiTree T, int i) {
    if (i >= T.ElemNum || T.SqBiTNode[i] == -1 || !g_ok) return;
    inorderCheck(T, 2*i + 1);                      // 左子树
    if (T.SqBiTNode[i] <= prev_val) {              // 当前必须严格大于 prev
        g_ok = 0;
        return;
    }
    prev_val = T.SqBiTNode[i];                     // 更新 prev
    inorderCheck(T, 2*i + 2);                      // 右子树
}

int isBST(SqBiTree T) {
    prev_val = INT_MIN;                            // 第一个被访问的结点没有"上一个"，用 -∞
    g_ok = 1;
    inorderCheck(T, 0);
    return g_ok;
}

从暴力解升级过来，坑主要有四个，第一个最致命：

prev 必须跨递归共享——用 static 全局，或者传指针 int *prev。写成按值传参 int prev，左子树里更新的 prev 一出栈就丢了，回到父结点比较时用的还是旧值，会把不合法的树误判成合法。这是本题阅卷视角下最典型的错法，也是暴力解升级时最容易忽略的语义变化：原来「上一个值」躺在数组里天然全局可见，现在它变成了要自己维护生命周期的状态。
必须严格大于：触发违反的条件写 cur <= prev。结点值均为正整数、BST 无重复，等值同样算违反；写成 < 会漏判等值相邻的情况。
prev 初值用 INT_MIN：第一个被访问的结点没有前驱；题面保证结点值全为正整数，INT_MIN 必然小于任何合法值，首结点必然通过。
两种空子树一个都不能少：漏了越界判定会读出数组边界，漏了 −1 判定会把 −1 当成结点值参与比较。!g_ok 的短路则让违反发现之后，所有还没展开的递归立即返回，不再做无意义的扫描。

复杂度：时间 $O (n)$ ，每个数组位置至多访问一次；辅助空间只剩 $O (h)$ 的递归栈（h 为树高，最坏 $O (n)$ ）——那条 $O (n)$ 的序列数组没有了。

两版对照跑一遍

用不合法的 T₂（[40, 50, 60, -1, 30, -1, -1, -1, -1, -1, 35]，答案 false）。先看暴力版——先把中序序列 [50, 30, 35, 40, 60] 完整收集完，回头检查才发现 30 ≤ 50：

加载可视化中...

再看 prev 版——访问到第二个结点（30）当场触发 30 ≤ 50，剩余递归全部短路：

加载可视化中...

演示为 JavaScript 版本，逻辑与上文 C 代码一一对应（JS 用闭包变量代替 C 的 static 全局，同样是跨递归共享）。

等价方法与升级空间

区间约束下传：另一条与中序 prev 法判分等价的路线——根的合法区间是 (−∞, +∞)，进左子树把上界收紧为父值、进右子树把下界收紧为父值，每个结点检查自己是否落在区间内。同样 $O (n)$ ，同样适用于顺序存储；用 INT_MIN/INT_MAX 当哨兵时注意边界的开闭。
下标公式是隐形考点：这道题真正筛人的地方在顺序存储——链式遍历谁都会写，0 起下标的 2i+1/2i+2 要现场推对，1 起的公式（2i/2i+1）直接照搬就错位了。空子树的两个条件同理，是这道题独有的细节分。

下一步

在 OJ 上把两版代码都提交跑一遍：ds-2022-41 判定顺序存储 BST
回到题库看这道题的完整解析与错因：真题库 · 数据结构

2022·41 顺序存储判 BST：从中序数组到一个 prev ​

题目 ​

第一步：把暴力解写对 ​

它值多少分 ​

暴力解的浪费在哪 ​

智慧化改造：把数组换成一个 prev ​

两版对照跑一遍 ​

等价方法与升级空间 ​

下一步 ​