每个孩子都左小右大，为什么还不是BST？2022年408的祖先约束-开发者社区

这道题要判断一棵二叉树是不是二叉搜索树。原题用数组存树，结点值都是正整数，-1表示空位。

我先想到的是逐个检查：左孩子比当前结点小，右孩子比当前结点大。一路检查下去，哪里不满足，就返回false。

这个办法看起来很顺，因为我们平时说二叉搜索树，经常就说“左小右大”。但这里的左和右，到底只指两个孩子，还是整棵子树？

我们先按这个办法检查一次

讨论时给出过这棵树：

40 / \ 20 60 \ 50

站在40这里看：左孩子20小于40，右孩子60大于40，能通过。

再站在20这里看：它的右孩子50大于20，也能通过。50和60下面都没有孩子，不会再发现不符合的比较。

检查哪一对	比较	结果
40与左孩子20	20<40	通过
40与右孩子60	60>40	通过
20与右孩子50	50>20	通过

按我最初的办法，这棵树就该返回true了。

但把视线从20移回40：50虽然是20的右孩子，却仍然在40的左子树里。它必须小于40，现在却大于40。

所以不是刚才那三次比较算错了，而是少比较了一个条件。BST要求整棵左子树的值都小于当前结点，不只是紧挨着的左孩子。

这里“40的左子树”包括哪些结点？从40的左边下去，先到20，再从20往右到50，这两个都还在40的左子树里。不是走过一次右边，就自动变成了40的右子树；要看这段路径最开始从40的哪一边进入。

换成中序遍历，能不能看出这个问题？

中序是先左子树，再当前结点，再右子树。

先从根40进左边。到20，它没有左孩子，所以先访问20；随后访问它右边的50。左子树结束，再回来访问40，最后访问右边的60。

得到的顺序是：

20 → 50 → 40 → 60

到40这里，我们已经看出问题：刚访问的是50，这次却变小了。

为什么中序能让这个问题显出来？因为40被安排在整个左子树的后面、整个右子树的前面。如果整棵左边都小于40，整棵右边都大于40，它就应该接在左边最大的值后面，再接上右边的值。

每个子树内部也是同样的安排。因此一棵严格的BST，中序访问的值会一直增大。反过来，如果中序严格递增，每个结点之前的左子树都比它小，之后的右子树都比它大，刚才遗漏的子树限制也就被检查到了。

一定要把这个序列存下来吗？

我先想的是遍历完，存下整个序列，再检查是不是递增。

但看我们刚才怎样发现问题的：只需要知道上一项是50，当前是40，就能失败，不用再回头看20。

所以用一个previous记着刚访问的值就够了。当前值比previous大，更新previous；否则立即返回false。相等也不行，因为这里检查的是严格BST。

这个previous必须随着整次中序访问继续走，不能每进一棵子树就重新清掉。我们正是要让左子树最后那个50，与回到根时的40相比较。

那我原来的先序办法，还能补好吗？

能。刚才漏的是祖先给出的限制，我们把它带到下面去。

从40往左走时，先记住：下面所有值都得小于40。

走到20，再往它的右边走时，又多了一条要求：下面的值还得大于20。

这两个条件不是二选一，而是要同时满足。所以50走到这里，实际要检查的是：

20 < 50 < 40

右半边不成立，这时就能失败。如果这里放的是30，两边都满足，就不会被这个条件挡住。

这样一层层走下去，要把每个祖先的值都存起来吗？也不必。所有“大于”的条件，只留下最严格的下界；所有“小于”的条件，只留下最严格的上界。它们合成一个范围。

根一开始没有限制。进40的左边，上界成为40；再进20的右边，下界成为20，上界仍是40。

代码就多带low和high两个参数。当前值x必须在它们之间；往左走，上界换成x，原下界保留；往右走，下界换成x，原上界保留。

这里的“保留”很重要。不能进入20的右边后只记x>20，又把上面的x<40丢掉。否则又回到我一开始漏条件的办法了。

原题的数组，怎样对应这棵树？

上面先画成树，是为了看清关系。原题不是链式存储，而是这样一个数组：

下标：0 1 2 3 4 数据：40 20 60 -1 50

根在下标0。下标i的左孩子在2i+1，右孩子在2i+2：20在下标1，所以它的右孩子在下标4，恰好是50。下标3的-1只是空位，不拿它参与大小比较。

这里有4个实际结点，但数组的有效区域占5格。原卷的ElemNum按占用的数组区域计算，中间的空位也算在内；若误填成4，就会把下标4的50漏掉。

下面把两种判断放在同一个C文件里。present先看下标是否还在有效区域，再检查是不是-1；其余过程就是刚才的中序比较和范围检查。

#include <limits.h> #include <stdbool.h> #include <stddef.h> #define MAX_SIZE 1024 typedef struct { int SqBiTNode[MAX_SIZE]; int ElemNum; } SqBiTree; bool present(const SqBiTree *t, size_t i) { return i < (size_t)t->ElemNum && t->SqBiTNode[i] != -1; } bool validInput(const SqBiTree *t) { return t && t->ElemNum > 0 && t->ElemNum <= MAX_SIZE && t->SqBiTNode[0] > 0; } bool checkInorder(const SqBiTree *t, size_t i, long long *prev) { if (!present(t, i)) return true; if (!checkInorder(t, 2 * i + 1, prev)) return false; long long x = t->SqBiTNode[i]; if (x <= *prev) return false; *prev = x; return checkInorder(t, 2 * i + 2, prev); } bool isBST_Inorder(const SqBiTree *t) { if (!validInput(t)) return false; long long prev = LLONG_MIN; return checkInorder(t, 0, &prev); } bool checkRange(const SqBiTree *t, size_t i, long long low, long long high) { if (!present(t, i)) return true; long long x = t->SqBiTNode[i]; if (x <= low || x >= high) return false; return checkRange(t, 2 * i + 1, low, x) && checkRange(t, 2 * i + 2, x, high); } bool isBST_Range(const SqBiTree *t) { return validInput(t) && checkRange(t, 0, LLONG_MIN, LLONG_MAX); }

中序版用指针传prev，是为了让更新对后续递归继续生效。范围版把low、high按值传给孩子，左右孩子分别接收自己的范围，不会把一边的限制改到另一边。

用long long表示边界，能把所有int值放在初始范围里面，不需要靠减1、加1制造边界。题意仍约定非空树、正整数结点值与正常树形；这段程序不是任意损坏数组的校验器。示例容量固定为1024。

两种方法最坏都要访问每个实际结点，时间O(V)，V是结点数。递归栈O(h)，h为树高；顺序存储的数组空位不等于实际结点，也不必每个空格都遍历一次。

顺序存储还要注意，一条很深的单侧链会让孩子下标迅速变大，浪费很多空位。这是存储方式的问题，不是把递归栈当作常数空间的理由。

题意按2022年408原卷第41题整理，原卷来自厦门工学院公开备考资料。下面保留我的解题复盘，C实现与验证是补充，不是官方答案。

附录：完整验证程序

参照先保存完整中序序列再检查，区别于待测的流式前驱和区间传递。覆盖重复键、INT_MAX和正常稀疏树形，不把损坏结构算进原题输入。

完整程序包含上面的题解函数和独立参照。保留源码，是为了读者能自己改输入、定位错误，不需要先读完它才能理解正文。

gcc -std=c11 -Wall -Wextra -Werror -pedantic -fsanitize=address,undefined -fno-omit-frame-pointer lab.c -o lab ./lab

#include <assert.h> #include <limits.h> #include <stdbool.h> #include <stddef.h> #include <stdio.h> #include <stdlib.h> #define MAX_SIZE 1024 typedef struct { int SqBiTNode[MAX_SIZE]; int ElemNum; } SqBiTree; bool present(const SqBiTree *t, size_t i) { return i < (size_t)t->ElemNum && t->SqBiTNode[i] != -1; } bool validInput(const SqBiTree *t) { return t && t->ElemNum > 0 && t->ElemNum <= MAX_SIZE && t->SqBiTNode[0] > 0; } bool checkInorder(const SqBiTree *t, size_t i, long long *prev) { if (!present(t, i)) return true; if (!checkInorder(t, 2 * i + 1, prev)) return false; long long x = t->SqBiTNode[i]; if (x <= *prev) return false; *prev = x; return checkInorder(t, 2 * i + 2, prev); } bool isBST_Inorder(const SqBiTree *t) { if (!validInput(t)) return false; long long prev = LLONG_MIN; return checkInorder(t, 0, &prev); } bool checkRange(const SqBiTree *t, size_t i, long long low, long long high) { if (!present(t, i)) return true; long long x = t->SqBiTNode[i]; if (x <= low || x >= high) return false; return checkRange(t, 2 * i + 1, low, x) && checkRange(t, 2 * i + 2, x, high); } bool isBST_Range(const SqBiTree *t) { return validInput(t) && checkRange(t, 0, LLONG_MIN, LLONG_MAX); } void collect(const SqBiTree *t, size_t i, int out[], size_t *n) { if (i >= (size_t)t->ElemNum || t->SqBiTNode[i] == -1) return; collect(t, 2 * i + 1, out, n); out[(*n)++] = t->SqBiTNode[i]; collect(t, 2 * i + 2, out, n); } int main(void) { size_t cases = 0; const int alphabet[5] = {-1, 1, 2, 3, INT_MAX}; for (size_t mask = 0; mask < 78125; mask++) { SqBiTree t = {.ElemNum = 7}; size_t x = mask; for (int i = 0; i < 7; i++) { t.SqBiTNode[i] = alphabet[x % 5]; x /= 5; } if (t.SqBiTNode[0] == -1) continue; int valid = 1; for (int i = 1; i < 7; i++) if (t.SqBiTNode[i] != -1 && t.SqBiTNode[(i - 1) / 2] == -1) valid = 0; if (!valid) continue; int values[7]; size_t n = 0; collect(&t, 0, values, &n); bool expected = true; for (size_t i = 1; i < n; i++) if (values[i] <= values[i - 1]) expected = false; assert(isBST_Inorder(&t) == expected); assert(isBST_Range(&t) == expected); cases++; } SqBiTree bad = {.SqBiTNode = {40, 20, 60, -1, 50}, .ElemNum = 5}; assert(!isBST_Inorder(&bad)); assert(!isBST_Range(&bad)); assert(!isBST_Inorder(NULL)); assert(!isBST_Range(NULL)); printf("PASS bst cases=%zu\n", cases); return 0; }

这次改写后，重新以严格编译选项和AddressSanitizer、UndefinedBehaviorSanitizer运行了上面的完整C程序，40804组树形与数值检查通过，输出如下。题解代码与此前版本逐字相同。assert不能通过-DNDEBUG关闭。