Code59 零基础 · 查找 · 53—56¶

2026-09-14 · 零基础讲解 · 先读题目与条件，再看示例和逐步讲解

先读第 0 课，再按每题“完整题干与条件 → 输入输出示例 → 人话讲解与状态推演 → 完整函数与逐句说明 → 自测”学习。题干整理和教学补充分别标注，原速查内容放在每题最后。

本篇对应全书第 53—56 题。重点是四种不同的约束：有序区间、BST 的全局大小关系、顺序树的存在性、AVL 的逐结点平衡。题意为转述，示例为本次补充；完整代码与原书块见各题回源。

读代码前：编译环境与类型¶

本章展示的是完整函数，不是每题各有一个 main 的独立程序。练习编译一题时，将所需类型、辅助函数与题目函数放在同一份学习用 C 文件里，再添加调用它的 main；第 0 课给了最小程序例子。常用标准头文件如下（它们提供打印、分配空间、真假类型、整数上限）：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <limits.h>
#define MAXSIZE 50

以下是本章使用的类型定义，不是要执行的解题步骤。字段含义见第 0 课；不要把不同章节重复的同名类型在同一文件中再定义多次。

/**/ #define MAXSIZE 50

typedef struct {
    int data[MAXSIZE];
    int length;
} SqList;

typedef struct BTNode {
    char data;
    struct BTNode *lchild;
    struct BTNode *rchild;
} BTNode, *BiTree;

53｜有序表二分查找（本章第 1 题）¶

题目与要求¶

题目（依据原题整理）：在有序顺序表中，使用二分查找寻找值为 key 的元素；给出非递归和递归两种实现。

已知条件：输入按非递减顺序排列的数组、有效范围和待查值 key。数组下标从 0 开始。

需要得到：下面锁定函数找到时返回从 1 开始的逻辑位置，即数组下标加 1；找不到返回 -1。

输入 → 输出示例（教学补充）：[2,4,6,8,10]，key=6 → 返回 3，因为 6 是第 3 个元素、数组下标为 2；key=7 → 返回 -1。

约定与提醒（教学补充）：返回位置的规则是本函数约定，不能与常见的“返回下标”版本混用。有多个同值元素时，下面实现找到任意一个即可，不保证是第一个；无序表不能直接使用二分查找。

题干回源：Code59 PDF 第 25 页；回源 · PDF 第 25 页 · b_25_0；PDF 第 25 页 · b_25_3；PDF 第 25 页 · b_25_1 。

1. 二分像猜数字，但每次淘汰有根据¶

输入升序表 [2,5,8,12,16]，key=12；输出逻辑位置 4，对应数组下标 3。key 就是要找的数，low/high 夹住还没排除的候选下标，mid 是其中靠左中点。

如果中间数 8 小于 12，8 左边的数更不可能是 12，所以连同 8 一起排除。这个推断要求表有序；无序表不能这样扔掉一半。

2. 同一个例子，把成功与失败各走一次¶

查询	当前 low..high	mid、读到的数	这步之后
找 12	0..4	2，值 8	8 太小，low=3
找 12	3..4	3，值 12	命中，返回 mid+1=4
找 9	0..4	2，值 8	low=3
找 9	3..4	3，值 12	12 太大，high=2
找 9	low=3、high=2	候选段已空	返回 -1

low>high 是区间空，不是数组里存了一个特殊标记。只剩一个候选时 low==high 仍必须检查。

3. 完整函数与逐句说明¶

代码段 1¶

↑ 回到本题题目

int binarySearch(SqList L, int key) {
    int low = 0;
    int high = L.length - 1;

    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (L.data[mid] == key)
            return mid + 1;  // 返回从 1 开始的逻辑位置
        if (L.data[mid] < key)
            low = mid + 1;
        else
            high = mid - 1;
    }

    return -1;
}

代码段 2¶

↑ 回到本题题目

int binarySearchRecursive(SqList L, int key, int low, int high) {
    if (low > high)
        return -1;

    int mid = low + (high - low) / 2;
    if (L.data[mid] == key)
        return mid + 1;
    if (L.data[mid] < key)
        return binarySearchRecursive(L, key, mid + 1, high);
    return binarySearchRecursive(L, key, low, mid - 1);
}

第一段非递归：边界先设成完整表 0..length-1。while 用 <=，覆盖只剩一个位置的情况。中点 low+(high-low)/2 与通常的平均位置一致，还减少两端直接相加溢出的风险。

先判断相等并 return；不等再看中值是否太小，是则 low=mid+1，否则 high=mid-1。已经比较过且不相等的 mid 可以排除，因此必须加一或减一，否则某些小区间可能不再缩小。循环空后 return -1。

第二段递归：用 low>high 作为失败终点；命中一样 return mid+1；不命中则调用同一函数只处理剩下的一半。外层的 return 把内层查到的位置原样传回，不是重新寻找。递归多了等待返回的调用栈，因此空间不是 O(1)。

4. 自己试一下¶

只有 [7] 找 7：low=high=0，while 仍进一次，返回 1。若写 < 就直接跳过，误报不存在。含重复的 [2,2,2] 中找 2，当前实现会返回某个命中位置，不承诺第一个；寻找最左或最右需要不同边界更新规则。

学懂后回看：结论、复杂度与回源¶

题意与结论：升序表中比较中间值，每轮排除不可能的一半。正式函数找到后返回从 1 开始的逻辑位置，没找到返回 -1。

思路推导：若中间值小于 key，则它及左边都不可能等于 key，令 low=mid+1；若大于 key，则令 high=mid-1。不是随便折半，而是利用排序为整段排除提供依据。

走一遍：[2,5,8,12,16] 找 12。初始 low=0,high=4,mid=2，中间值 8 小于 12，排除下标 0..2；剩 [3,4]，mid=3，找到 12，返回 mid+1=4。找 9 则接着因 12 太大令 high=2，变为 low>high，返回 -1。

代码抓手与正确性：闭区间版本循环条件为 low<=high；中点用 low+(high-low)/2，避免两端直接相加的溢出风险。若 key 存在，始终位于当前候选区间内；每次排除都不会丢掉 key，区间空时才能宣布失败。

复杂度与易错点：时间 O(log n)；非递归空间 O(1)，递归栈 O(log n)。空表初始 high=-1，直接失败。表含重复值时返回某一次命中的位置，不保证第一个或最后一个。原表若无序，不能只因为想“更快”就套二分。

回源：PDF 第 25 页；回源 · PDF 第 25 页 · b_25_0；PDF 第 25 页 · b_25_3；PDF 第 25 页 · b_25_8；PDF 第 25 页 · b_25_1；PDF 第 25 页 · b_25_9 。正式代码

54｜链式二叉树是否为 BST（本章第 2 题）¶

题目与要求¶

题目（依据原题整理）：给定一棵用二叉链表保存的二叉树，判断它是否为二叉搜索树，也称二叉排序树，简称 BST。

已知条件：结点保存数值关键字。按本讲解的严格 BST 约定，每个结点左子树的所有值都小于它，右子树的所有值都大于它，两棵子树也必须符合该规则。

需要得到：整棵树符合规则返回真，否则返回假；不要求调整树或插入新结点。

输入 → 输出示例（教学补充）：根 5，左孩子 3、右孩子 7 → 真；若再给结点 3 添加右孩子 6 → 假，因为 6 位于根 5 的左子树，却大于 5。

约定与提醒（教学补充）：不能只比较结点和它的直接孩子，必须满足全部祖先的限制。这里不允许相等关键字，空树按真处理。

题干回源：Code59 PDF 第 25—26 页；回源 · PDF 第 25 页 · b_25_2；PDF 第 25 页 · b_25_4；PDF 第 26 页 · b_26_0 。

1. BST 的约束作用于整棵子树，不只是相邻两点¶

二叉搜索树要求：一个结点左边的全部后代都小于它，右边的全部后代都大于它；每个子树也同样满足。这里相等关键字不接受。

根 10、左孩子 5、5 的右孩子 12，看相邻关系似乎 5<10、12>5 都对，但 12 仍在 10 的左子树中，必须小于 10，因此不是 BST。

2. 两种检查，各自保留哪一份信息¶

方法	对反例怎样检查	在哪里发现错误
中序递增	依次看到 5、12、10	10 不大于前一个 12
合法区间	10 的左侧必须在 (-∞,10)；5 的右侧进一步缩成 (5,10)	12 不在 (5,10)

previous 存中序“前一个已经访问的值”，hasPrevious 表示前值是否存在。区间法 low/high 存全部祖先累积下来的边界，区间是开区间，等于边界也不行。

3. 完整函数与逐句说明¶

代码段 1¶

↑ 回到本题题目

bool isBSTInorderImpl(BiTree root, bool *hasPrevious, int *previous) {
    if (root == NULL)
        return true;

    if (!isBSTInorderImpl(root->lchild, hasPrevious, previous))
        return false;

    if (*hasPrevious && root->data <= *previous)
        return false;
    *previous = root->data;
    *hasPrevious = true;

    return isBSTInorderImpl(root->rchild, hasPrevious, previous);
}

bool isBSTInorder(BiTree root) {
    bool hasPrevious = false;
    int previous = 0;
    return isBSTInorderImpl(root, &hasPrevious, &previous);
}

代码段 2¶

↑ 回到本题题目

bool isBSTByRange(BiTree root, long long low, long long high) {
    if (root == NULL)
        return true;

    long long value = root->data;
    if (value <= low || value >= high)
        return false;

    return isBSTByRange(root->lchild, low, value)
        && isBSTByRange(root->rchild, value, high);
}

中序辅助函数空树返回 true。先递归检查左子树，若失败立即向上传 false；然后如果已经有 previous 且当前 data<=previous，说明没有严格递增，返回 false。通过后把 previous 更新成当前 data、hasPrevious 设真，最后返回右子树检查结果。

这两个参数传的是地址，所以左子树最后访问的值能被父层接着比较；如果只传普通值副本，父层看不到子树更新，中序整体关系就可能丢失。包装函数先设 hasPrevious=false，previous=0 只是初值，尚未参与有效比较，再把地址传入。

区间法先判空，再取当前数值；落在区间外或等于边界则拒绝。左递归的上界变当前 value，下界仍沿用祖先的 low；右递归下界变 value，上界仍为 high。两边都通过才返回 true。第一次用 LLONG_MIN/LLONG_MAX 给一个足够宽的范围。

4. 自己试一下¶

把反例的 12 改成 7：中序 5、7、10 严格递增，7 也在 (5,10)，变成合法。根 10、右孩子也为 10：这份严格定义不接受。普通树类型的 data 是 char，任意整数版本要使用相应整数数据域，不要把字符串数字和数值排序混为一谈。

学懂后回看：结论、复杂度与回源¶

题意与结论：本题按严格 BST 判断：左子树所有值小于根，右子树所有值大于根，不接收相等关键字。可检查中序严格递增，也可向下传合法开区间。

思路推导：只比较“左孩子<父、右孩子>父”是不够的，因为更深的结点还受所有祖先约束。中序把所有结点连成整体序列；区间法则把这些祖先约束逐层累积。

走一遍（反例）：根为 10，左孩子 5，5 的右孩子 12。局部关系有 5<10、12>5，都看似正确，但 12 在 10 的左子树中，仍必须小于 10，因此不是 BST。中序为 [5,12,10]，到 10 时不递增；区间法给 12 的区间是 (5,10)，也会拒绝。

代码抓手与正确性：中序法先处理左树，再比较当前值与 previous，最后处理右树；hasPrevious 表示是否已有前一个值，不能把 previous 初值 0 当作有效边界。区间法当前值 x 合格后，左递归 (low,x)，右递归 (x,high)，保持全部祖先限制。

复杂度与易错点：两法时间 O(n)、栈 O(h)；空树返回 true。当前通用树结构的数据域是 char，算法按其可比较的值判断；例子用小整数说明大小关系。若处理任意整数关键字，应使用相应数值结点类型，并以更宽上下界避免合法极值与哨兵冲突。允许重复关键字的工程 BST 必须另定相等值放哪边，本题不采用那种定义。

回源：PDF 第 25—26 页；回源 · PDF 第 25 页 · b_25_2；PDF 第 25 页 · b_25_4；PDF 第 25 页 · b_25_10；PDF 第 26 页 · b_26_0；PDF 第 26 页 · b_26_4 。正式代码

55｜顺序存储二叉树是否为 BST（本章第 3 题，2022）¶

题目与要求¶

题目（依据原题整理）：给定一棵采用顺序存储结构的二叉树，判断它是否为二叉搜索树，即每个结点都满足左子树所有关键字更小、右子树所有关键字更大的条件。

已知条件：根在下标 0，左右孩子位置为 2i+1、2i+2。下面校订结构用 Node[] 保存数值、exists[] 单独标记槽位是否有结点，storageLength 表示有效存储范围长度。

需要得到：合法树结构内所有实际结点符合严格 BST 规则时返回真，否则返回假。

输入 → 输出示例（教学补充）：Node=[2,-1,3]，exists=[true,true,true] → 根 2 的左孩子为 -1、右孩子为 3，返回真；Node=[2,4,3] 且三槽都存在 → 返回假。

约定与提醒（教学补充）：原资料用 -1 作为空位标记；锁定稿将存在性独立出来，因此示例的 -1 是实际关键字。有效存储范围不是实际结点个数；本函数假定数组原本表示一棵合法树，不额外修复空父结点下面的孤立数据。

题干回源：Code59 PDF 第 26 页；回源 · PDF 第 26 页 · b_26_1；PDF 第 26 页 · b_26_6 。

1. 换成数组后，大小规则并没有变¶

仍检查每个结点值是否满足全部祖先限制，只是孩子地址变成孩子下标。下标 i 的左、右孩子在 2i+1、2i+2；值通过 node[i] 读取，位置是否存在通过 exists[i] 读取。

输入有效位置 0:10、1:5、2:15、4:7，其余不存在。输出 true。如果下标 4 改成 12，则输出 false，因为它在根 10 的左子树中。

2. 把位置、存在标记和值分开¶

index	exists	node 值	此时合法范围	判断
0	真	10	极宽范围	合法，向两边传界
1	真	5	小于 10	合法
3	假	无意义	小于 5	空，不读值，返回真
4	真	7	大于 5 且小于 10	合法；改 12 就失败
2	真	15	大于 10	合法

storageLength 至少为 5 才覆盖下标 4，即使真实结点只有 4 个。这个变量不是“总共有几个结点”。

3. 完整函数与逐句说明¶

代码段 1¶

↑ 回到本题题目

typedef int ElemType;

typedef struct {
    ElemType node[MAXSIZE];
    bool exists[MAXSIZE];
    int storageLength;  // 已使用存储区长度，即最大可能下标 + 1
} SqBiTree;

bool isArrayBST(SqBiTree T, int index,
                long long low, long long high) {
    if (index >= T.storageLength || !T.exists[index])
        return true;

    long long value = T.node[index];
    if (value <= low || value >= high)
        return false;

    return isArrayBST(T, 2 * index + 1, low, value)
        && isArrayBST(T, 2 * index + 2, value, high);
}

typedef int ElemType 只是给 int 起别名。结构中 node 存数，exists 存真假，storageLength 限制允许访问的下标范围。函数先判断越界，或当前位置不存在，空子树自动合格并 return true。

存在时才取 value。若 value<=low || value>=high 则不在合法开区间，返回 false。左右递归改变下标与一侧边界，另一侧边界必须继续保留，防止忘记祖先要求。首次调用下标 0、宽上下界。

4. 自己试与为什么不拿 -1 当空¶

根为 0、左孩子为 -1，在整数 BST 中本来合法。如果用 node[i]==-1 判断空，就把一个真实结点当没了；exists 单独记录解决这个冲突。若 exists[1]=false 却 exists[4]=true，则出现空父结点下面的孤立后代，不是本算法前提中的合法树表示。

学懂后回看：结论、复杂度与回源¶

题意与结论：大小约束仍按上一题的区间法，孩子位置则改为 2i+1、2i+2。先确认槽位真实存在，再检查值。

思路推导：存储方式只改变“如何找到孩子”，不改变 BST 定义。当前值 x 必须落在 (low,high)；左子树继续受上界 x 限制，右子树受下界 x 限制。

走一遍：数组位置 0=10、1=5、2=15、4=7，其余不存在，是合法 BST。到下标 4 时，它是左孩子 5 的右孩子，合法区间为 (5,10)，7 在区间内。若把下标 4 改为 12，虽然 12>5，仍因 12>=10 被拒绝。

代码抓手与正确性：先判断 index>=storageLength || !exists[index]，为空则返回 true；再读 node[index]。storageLength 是最大可能下标加一，不是实际结点数。例子仅有 4 个结点，但必须覆盖下标 4，所以存储长度至少为 5。

复杂度与易错点：合法结构中按可达结点数计为 O(n)、栈 O(h)，按存储长度 N 给粗上界则 O(N)。校订版用独立 exists 数组，不把 -1 当空值，因此允许合法关键字 -1。默认不存在“空父结点下面还有有效孩子”的畸形表示；若需审计任意数组结构，应另验这一点。

回源：PDF 第 26 页；回源 · PDF 第 26 页 · b_26_1；PDF 第 26 页 · b_26_6 。正式代码

56｜BST 是否平衡（本章第 4 题）¶

题目与要求¶

题目（依据原题整理）：给定一棵二叉排序树，判断它是否为平衡二叉树，即每个结点的左、右子树高度之差的绝对值都不超过 1。

已知条件：输入已经保证是 BST；空树高度为 0，单结点树高度为 1。

需要得到：全树每个结点都平衡时返回真，任何一个结点失衡时返回假。

输入 → 输出示例（教学补充）：根 2 的左右孩子为 1、3 → 真；根 3 只有左孩子 2，而 2 又只有左孩子 1 → 假，根的左右子树高度分别为 2 和 0。

约定与提醒（教学补充）：这题只判定，不做旋转修复。只检查根的高度差不够；如果输入并未保证 BST，还要另外做第 54 题的大小关系检查，不能仅凭平衡判为 AVL 树。

题干回源：Code59 PDF 第 26 页；回源 · PDF 第 26 页 · b_26_2 。

1. 平衡检查不是比较左右结点数量¶

题设先保证它已经是 BST，接着要求每个结点左右子树高度差最多 1。高度是层数，不是结点数；空子树高度 0、单个叶子高度 1。

辅助函数 balancedHeight 有两种返回含义：非负数表示“这棵子树平衡，且高度是这个数”；-1 表示“已经发现不平衡”。把这两件事一趟同时做，避免每层重新数高度。

2. 用一条链看 -1 怎么向上传¶

BST 根 3、左孩子 2、2 的左孩子 1，其他为空。

当前结点	左返回	检查	本层返回
1	0	差 0，平衡	高度 1
2	1	差 1，平衡	高度 2
3	2	差 2，超出 1	-1

主判断函数看到不是有效高度而是 -1，便返回 false。若失衡发生在更低处，不需要根自己再有大高度差，失败信号照样一路上报。

3. 完整函数与逐句说明¶

代码段 1¶

↑ 回到本题题目

int balancedHeight(BiTree root) {
    if (root == NULL)
        return 0;

    int leftHeight = balancedHeight(root->lchild);
    if (leftHeight == -1)
        return -1;

    int rightHeight = balancedHeight(root->rchild);
    if (rightHeight == -1)
        return -1;

    if (abs(leftHeight - rightHeight) > 1)
        return -1;

    return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}

bool isBalancedBST(BiTree root) {
    return balancedHeight(root) != -1;
}

root 为空返回高度 0；递归取 leftHeight，若是 -1 立即失败，不必继续浪费时间；右边同理。两边都有正常高度后，abs 计算高度差绝对值，超过 1 则失败。

通过时三目表达式选较大高度，再加 1 算上当前这一层。注意 -1 是失败信号，必须先排除，不能把它拿进 max 当正常高度。包装函数只问 balancedHeight(root)!=-1，将“有效高度/失败”转成真假。

4. 自己试与别误读函数名¶

根 2、左叶 1、右叶 3：两边都返回 1，根返回 2，主函数 true。只检查根高度差不够，下面任何一层也要平衡。这个函数本身没有检查值大小；如果输入任意树而非已保证 BST，只凭它不能判定“既是 BST 又平衡”，还要配合上一题。

学懂后回看：结论、复杂度与回源¶

题意与结论：题设已经保证输入为 BST，只检查每个结点的左右子树高度差是否不超过 1。后序一次返回“高度或失衡标记 -1”。

思路推导：直观方法在每个结点重新计算两子树高度，长链上会反复遍历同一批后代，最坏 O(n²)。让孩子在检查平衡时顺便返回高度，父结点就不需要再扫描一次。

走一遍：BST 3←2←1 是一条向左的链。叶子 1 返回高度 1；结点 2 的左右高度为 1、0，差 1，返回高度 2；根 3 的左右高度为 2、0，差 2，返回 -1，整树不平衡。若根 2 左为 1、右为 3，则两侧高度都 1，返回高度 2，平衡。

代码抓手与正确性：空树返回 0；先取左高度，若为 -1 立刻上报；再取右高度，同样检查；两边都有效且差不超过 1，才返回 max(left,right)+1。真实高度非负，所以 -1 不会与正常结果冲突。任一子树失衡会一直传到根。

复杂度与易错点：时间 O(n)、栈 O(h)，最坏链状 h=n。只检查根的高度差不够，内部子树也可能失衡。函数名虽含 BST，这段代码并未验证大小关系；若输入只是任意二叉树，要先或同时验证 BST 性质。本题要求判断，不要求做 AVL 旋转修复。

回源：PDF 第 26 页；回源 · PDF 第 26 页 · b_26_2；PDF 第 26 页 · b_26_8 。正式代码