第一次见到这道题是在数据结构的习题册里“判断二叉树是否为二叉排序树”“判断二叉树是否为平衡二叉树”。我当时觉得这不难左右子树比一比、高度算一算不就有答案了吗后来真正用 C 语言写代码才发现问题远比想象的细——判断二叉排序树的关键不是“当前结点和左右孩子的比较”而是祖先结点一路传下来的区间约束判断平衡二叉树也不只是算高度而是要设计一个能在后序遍历里一边返回高度、一边暴露不平衡状态的递归函数。这两个判断题是二叉树递归思想的经典应用也是很多课程设计、笔试和面试里的高频题。这篇文章把两个问题的完整思路、可运行的 C 语言代码以及我自己写题时踩过的坑逐个讲清楚适合正在备考数据结构、刷题练递归的朋友参考。1. 两个判断题里最容易被坑的定义边界很多题不是不会写而是对“二叉排序树”和“平衡二叉树”的理解停留在表面导致代码写了半天边界情况一跑就翻车。先把定义抠清楚后面所有代码才有依据。1.1 二叉排序树的“所有”两个字卡掉了多少人二叉排序树BST的经典定义是要么是空树如果左子树不空那么左子树上所有结点的值均小于根结点的值如果右子树不空那么右子树上所有结点的值均大于根结点的值同时左右子树本身也必须是二叉排序树。注意“所有”两个字。很多人写判断时只看“左孩子小于根、右孩子大于根”这个认知会留下大坑。看下面这棵树10 / \ 5 15 / \ 6 20单看每一对父子关系全是对的5 小于 1015 大于 106 小于 1520 大于 15。但整棵树不是二叉排序树因为 6 在根结点 10 的右子树里却比 10 小。也就是说“左子树所有值都小于根”是一个全局约束它会在递归向下时逐层传递一个结点不仅要比父亲大还要比所有“右转过来的祖先”大比所有“左转过来的祖先”小。这个反例我印象极深。某次课程作业里我就用“只比较父子”的写法构造了一棵类似结构的树结果程序自信地输出了“是二叉排序树”。直到老师提醒“局部有序不等于整体有序”我才意识到问题出在约束传递上。1.2 平衡二叉树空树也算平衡别漏掉基准情况平衡二叉树通常指每个结点的左右子树高度差绝对值不超过 1并且左右子树本身也平衡。它有两个容易被忽略的基准空树是平衡的单个结点也是平衡的。正因为空树算平衡判断函数的递归出口通常写成if (root NULL) return 1;并且计算高度时空树高度定义为 0。这两个约定看起来很基础但真的会有人把空树的平衡判断写成返回 0导致一棵空树被判成“不平衡”后面所有正确结果全部被带偏。还要区分一组概念完全二叉树、满二叉树、平衡二叉树。完全二叉树一定平衡但平衡树不一定是完全二叉树。比如一棵左边深度为 2、右边深度为 1 的树每个结点高度差都满足约束但它并不是教科书里那种“从左到右连续填充”的完全形态。所以判断平衡时不要拿“有没有缺结点”来脑补只看高度差。1.3 排序和平衡是两个独立维度别混为一谈二叉排序树关心的是“值的大小顺序”平衡二叉树关心的是“高度分布”。一棵二叉排序树完全可能退化成长链例如 1 → 2 → 3 → 4 这样一路向右延伸它的中序确实是递增的但它肯定不是平衡二叉树因为根结点右子树高度为 n-1左子树高度为 0差值远超 1。反过来一棵平衡树也保证不了有序。假设某个结点的左子树无论怎么填只要高度和右子树差不多它就能满足平衡约束但里面的值和根的大小关系可能完全乱掉。所以这两个判断题是两个独立函数写的时候也不要默认“一棵树如果满足 BST 就一定平衡”或“平衡就一定有序”。很多题目会把两个问题放在同一道大题里但考察点完全是两道题。2. 二叉排序树判断的正解从逐个比较到区间约束先把最流行的错误写法亮出来再给出两种正确解法。只有知道错在哪才能真正理解为什么需要区间约束。2.1 最流行的错误写法只比较父子结点很多初学者的第一版代码长这样int isBSTWrong(BiTree root) { if (root NULL) return 1; if (root-lchild root-lchild-data root-data) return 0; if (root-rchild root-rchild-data root-data) return 0; return isBSTWrong(root-lchild) isBSTWrong(root-rchild); }这段代码的问题非常隐蔽它只检查了当前结点和直接孩子的大小关系完全没有检查孙子、曾孙那一层。回到前面的反例树10、5、15、6、20这个函数会一路返回“真”因为 6 不和 10 直接比较它只和 15 比较。为什么会有这种思维惯性因为画树的时候大部分人眼睛先看“相邻两层”忽略了二叉排序树定义里强调的是“子树上的所有结点”。一个结点只要存在于某祖先的左子树里它就受这条左转路径上的所有上限约束存在于右子树里就受所有下限约束。只比较父子相当于把一条完整的约束链砍成了碎片。2.2 正确解法一递归时传递上下界区间把约束看作一个取值区间函数从根开始带着整个区间递归整棵树的初始区间是“负无穷到正无穷”。递归进入左子树时上限收紧为当前结点值因为左子树所有值都必须小于当前结点。递归进入右子树时下限收紧为当前结点值因为右子树所有值都必须大于当前结点。对应代码int isBSTByRange(BiTree root, long long min, long long max) { if (root NULL) return 1; if (root-data min || root-data max) return 0; return isBSTByRange(root-lchild, min, root-data) isBSTByRange(root-rchild, root-data, max); }调用时传入isBSTByRange(root, LLONG_MIN, LLONG_MAX);这里有一个我踩过的坑为什么边界类型用long long而不是int如果直接用INT_MIN和INT_MAX一旦树里某个结点的值恰好等于INT_MIN第一层判断root-data INT_MIN就会为真把一棵合法单结点树误判成非法。用long long并把边界设为LLONG_MIN、LLONG_MAX就能留出足够余量避免边界值误伤。如果你不想依赖long long也可以用“指针表示无界”的方案传入BiTNode *minNode和BiTNode *maxNode为NULL表示没有边界比较时先判断指针是否为NULL再比较root-data与minNode-data、maxNode-data的大小。这个方案在值范围受限的系统里更安全但写起来会多几行条件判断笔试时按个人习惯选择即可。2.3 正确解法二中序遍历严格递增二叉排序树还有一个等价性质中序遍历结果严格递增。利用这个性质可以一边递归中序遍历一边检查当前结点值是否大于上一个访问值。因为递归会跨层共享状态C 语言里必须传入一个指针变量prev来保存上一个访问值int isBSTByInorder(BiTree root, long long *prev) { if (root NULL) return 1; if (!isBSTByInorder(root-lchild, prev)) return 0; if (root-data *prev) return 0; *prev root-data; return isBSTByInorder(root-rchild, prev); }调用方式long long prev LLONG_MIN; isBSTByInorder(root, prev);为什么prev初值也用LLONG_MIN和区间法的理由一样如果树中第一个访问的结点恰好是INT_MIN用INT_MIN作为初值第一轮root-data prev就成立代码会把合法树判成非法。写成LLONG_MIN之后再和int比较编译器会做整型提升不会误伤。还要提醒一个细节递归左子树时如果已经返回 0必须立刻return 0不要在继续往右走的同时更新prev。顺序一旦乱掉可能会用一个错误的前驱值去比较右子树导致结果不可信。2.4 两种方法怎么选实际对比区间法和中序法的时间复杂度都是 O(n)区别主要在编码风格和可扩展性上。对比项区间法中序法核心思路每层递归收紧上下界中序遍历形成的序列有序额外参数min、max 两个边界一个 prev 指针边界值处理用 long long 或指针表示无界prev 初值也需要大范围类型可扩展性只能做判断可以顺便输出有序序列、找第 k 小代码量较短逻辑直观稍长但思路好理解如果题目只要求判断是否是二叉排序树我个人推荐区间法代码短、不容易写乱。如果后续还要基于中序做其他操作比如输出升序序列或查找中序第 k 个元素那中序法可以一次复用写成独立的遍历函数更顺。3. 平衡二叉树判断一次后序遍历拿捏高度O(n) 解决判断平衡树的核心难点不是递归本身而是如何避免重复计算子树高度。朴素写法能跑但复杂度不够漂亮。3.1 “先算高度再判断”的朴素写法为什么慢最常见的第一版代码如下int treeHeight(BiTree root) { if (root NULL) return 0; int l treeHeight(root-lchild); int r treeHeight(root-rchild); return (l r ? l : r) 1; } int isBalancedSlow(BiTree root) { if (root NULL) return 1; if (abs(treeHeight(root-lchild) - treeHeight(root-rchild)) 1) return 0; return isBalancedSlow(root-lchild) isBalancedSlow(root-rchild); }这个版本能正确工作但性能却是 O(n²)。原因在于isBalancedSlow对每个结点都调用一次treeHeight而treeHeight本身又会对子树的所有结点做一次遍历。一个结点既要在“判断自己在不在平衡状态”时被算高度又要在“父亲判断平衡”时被算一遍还会在“祖父判断平衡”时再被算一遍。最坏情况是一棵高度为 n 的斜树根结点调用treeHeight遍历 n 个结点第二层遍历 n-1 个结点第三层遍历 n-2 个结点累加起来是一个等差数列求和复杂度就是 O(n²)。练习时数据量小看不出问题一旦树有几万个结点递归栈和重复计算都会变得非常难受。3.2 用 -1 作为哨兵后序遍历同时返回高度优化思路其实很简单既然判断平衡需要高度那就在递归处理子树时把子树高度直接“带回来”。后序遍历左、右、根天然适合做这件事因为只有先知道左右子树的高度才能判断当前根是否平衡。函数返回值设计为返回子树高度如果发现子树不平衡则返回 -1。这样一棵子树是否平衡直接被编码进返回值里不用额外开全局变量也不用传指针进来。int getHeightIfBalanced(BiTree root) { if (root NULL) return 0; int leftH getHeightIfBalanced(root-lchild); if (leftH -1) return -1; int rightH getHeightIfBalanced(root-rchild); if (rightH -1) return -1; if (abs(leftH - rightH) 1) return -1; return (leftH rightH ? leftH : rightH) 1; }对外再包一层int isBalancedTree(BiTree root) { return getHeightIfBalanced(root) ! -1; }这里的顺序是刻意安排的先递归左子树如果左子树已经不平衡立刻返回 -1不再递归右子树。这种提前结束能省掉大量无效遍历是实际跑起来性能更好的关键。空树返回 0叶子结点返回 1完全符合高度定义。3.3 -1 这个哨兵值会不会和真实高度冲突这是一个值得展开讲的问题。二叉树高度最小是 0空树叶子结点是 1任何合法子树的高度都不可能为负数。所以用 -1 表示“不平衡”不会和真实高度混淆是安全的哨兵值。如果你在面试现场面试官可能会追问“为什么返回值不直接设计成布尔型”。可以这样回答如果只返回布尔值父结点就没有办法知道当前子树的高度必须再调用一次getHeight就会退回朴素写法的 O(n²)。而返回高度或者 -1本质上是把“平衡性”和“高度”两个信息压缩在一个整数里。如果面试官要求更语义化的写法也可以改成返回一个结构体typedef struct { int height; int balanced; } Result;每次递归返回Result代码更可读但结构体赋值和判断会多一点代码。笔试手写 C 时-1 哨兵方案最省事我个人常年在代码里写这个版本。3.4 平衡判断里最容易出现的三处低级错误第一处是忘记检查子树返回值-1。如果不做if (leftH -1) return -1;后面会拿-1去参与高度差计算结果完全失真。第二处是abs漏掉或写错高度差一定要取绝对值否则左高右低和右高左低会有一个方向永远发现不了。第三处是递归顺序写成了前序或者中序当前根还没拿到子树高度就开始比较自然拿不到正确信息。这三类错误我在帮同学排查代码时都见过每一条都值得在写完后自查一遍。4. 完整的 C 语言实现与测试用例前面把原理和关键代码都讲清楚了这一节给出一份可以直接复制运行的完整测试工程。结构体、辅助函数、三个判断函数、主函数测试用例一步到位。4.1 数据结构定义与建树辅助函数#include stdio.h #include stdlib.h #include limits.h typedef struct BiTNode { int data; struct BiTNode *lchild; struct BiTNode *rchild; } BiTNode, *BiTree; BiTree createNode(int val) { BiTree node (BiTree)malloc(sizeof(BiTNode)); node-data val; node-lchild node-rchild NULL; return node; }createNode只是一个辅助函数避免在构造测试树时反复写三行 malloc 赋值。实际工程中建树可能来自输入序列但本题的重点是判断所以直接把树结构手动搭出来最清晰。4.2 三个判断函数完整版// 区间法判断二叉排序树 int isBSTByRange(BiTree root, long long min, long long max) { if (root NULL) return 1; if (root-data min || root-data max) return 0; return isBSTByRange(root-lchild, min, root-data) isBSTByRange(root-rchild, root-data, max); } // 中序法判断二叉排序树 int isBSTByInorder(BiTree root, long long *prev) { if (root NULL) return 1; if (!isBSTByInorder(root-lchild, prev)) return 0; if (root-data *prev) return 0; *prev root-data; return isBSTByInorder(root-rchild, prev); } // 平衡二叉树判断返回 -1 表示不平衡否则返回子树高度 int getHeightIfBalanced(BiTree root) { if (root NULL) return 0; int leftH getHeightIfBalanced(root-lchild); if (leftH -1) return -1; int rightH getHeightIfBalanced(root-rchild); if (rightH -1) return -1; if (abs(leftH - rightH) 1) return -1; return (leftH rightH ? leftH : rightH) 1; } int isBalancedTree(BiTree root) { return getHeightIfBalanced(root) ! -1; }中序法调用时注意先声明long long prev LLONG_MIN;再把prev传给函数。区间法直接传LLONG_MIN和LLONG_MAX这两个宏定义在limits.h头文件里。4.3 测试用例设计每一棵树想验证什么我准备了七组测试树覆盖正常情况、反例、边界值、重复值和退化情况。编号树描述预期 BST预期平衡树1标准 BST10、5、15、2、7、12、20是是树2局部有序反例10、5、15、6、20否是树3含重复值10、10、15按无重复定义否是树4平衡且有序10、5、20、3、7是是树5有序但退化10、5、20、3、4是否树6空树是是树7单结点树是是树2是全文反复使用的反例它专门用来验证“只比较父子”的错误写法是否被识别出来。树5需要重点看一下结构10 / \ 5 20 / 3 \ 4左子树从 3 到 4 到 5 形成一条下行链高度是 3右子树高度是 1差值超过 1所以不是平衡树但中序遍历 3、4、5、10、20 严格递增所以是 BST。4.4 主函数与运行结果int main() { BiTree t1 createNode(10); t1-lchild createNode(5); t1-rchild createNode(15); t1-lchild-lchild createNode(2); t1-lchild-rchild createNode(7); t1-rchild-lchild createNode(12); t1-rchild-rchild createNode(20); BiTree t2 createNode(10); t2-lchild createNode(5); t2-rchild createNode(15); t2-rchild-lchild createNode(6); t2-rchild-rchild createNode(20); BiTree t3 createNode(10); t3-lchild createNode(10); t3-rchild createNode(15); BiTree t4 createNode(10); t4-lchild createNode(5); t4-rchild createNode(20); t4-lchild-lchild createNode(3); t4-lchild-rchild createNode(7); BiTree t5 createNode(10); t5-lchild createNode(5); t5-rchild createNode(20); t5-lchild-lchild createNode(3); t5-lchild-lchild-rchild createNode(4); BiTree t6 NULL; BiTree t7 createNode(10); BiTree trees[] {t1, t2, t3, t4, t5, t6, t7}; int i; for (i 0; i 7; i) { long long prev LLONG_MIN; int bst1 isBSTByRange(trees[i], LLONG_MIN, LLONG_MAX); int bst2 isBSTByInorder(trees[i], prev); int bal isBalancedTree(trees[i]); printf(Tree %d: RangeBST%d InorderBST%d Balanced%d\n, i 1, bst1, bst2, bal); } return 0; }运行结果如下Tree 1: RangeBST1 InorderBST1 Balanced1 Tree 2: RangeBST0 InorderBST0 Balanced1 Tree 3: RangeBST0 InorderBST0 Balanced1 Tree 4: RangeBST1 InorderBST1 Balanced1 Tree 5: RangeBST1 InorderBST1 Balanced0 Tree 6: RangeBST1 InorderBST1 Balanced1 Tree 7: RangeBST1 InorderBST1 Balanced1区间法和中序法输出的 BST 判断结果完全一致这说明两套思路在逻辑上是等价的。树6空树和树7单结点都同时通过三个判断基准情况没有被漏掉。5. 考试与面试中的变体思路重复值、空树、复杂度的追问这类题单纯跑通还不是终点面试官和考试题经常会换个语义来问或者要求你换一种实现方式。下面几个变体是我实际遇到过或者帮别人辅导时见过的高频延伸。5.1 遇到“重复值算不算 BST”怎么办这题的答案一律是“看题面定义”。没有重复值的前提下BST 要求严格小于和严格大于所以中序序列严格递增区间法边界用和判断。如果题目允许重复并采用“左子树小于等于根、右子树大于根”这类约定那么中序法要把root-data *prev改成root-data *prev区间法的左边界判断也要同步调整。最稳妥的做法是在代码注释里写明自己的假设/* 按常见无重复结点定义左小右大 */手撕代码时如果面试官没有明确说我建议直接先问一句“树里允许重复值吗”。这句话本身就能让面试官觉得你对语义敏感比默默写一个版本然后被测试用例打脸强得多。5.2 空树和单结点先确认约定再写注释不同教材对空树是不是二叉排序树的表述不完全一致但绝大多数递归定义里空树算 BST也算平衡树。如果你不放心可以在注释里写清楚按“空树合法”的约定返回真如果题目要求空树返回假把root NULL的返回值改成 0 即可。单结点也一样它既是 BST 又是平衡树。很多边界错误恰恰是在这些最“简单”的例子上翻车的测试用例一定要包含它们。5.3 如果面试官要求非递归版本递归版本的缺点是深度过大时可能栈溢出。中序遍历的 BST 判断可以改成显式栈模拟int isBSTNonRecursive(BiTree root) { BiTree stack[1024]; int top -1; long long prev LLONG_MIN; BiTree cur root; while (cur ! NULL || top ! -1) { while (cur ! NULL) { stack[top] cur; cur cur-lchild; } cur stack[top--]; if (cur-data prev) return 0; prev cur-data; cur cur-rchild; } return 1; }这段代码的思路就是把递归中序遍历改成手工压栈函数栈变成显式数组栈。空间复杂度 O(n)。如果继续追问能不能做到 O(1) 空间那就涉及线索化思想的 Morris 遍历它能利用叶子结点的空指针作为临时前驱实现常数空间的遍历但理解成本更高面试时通常作为加分项出现。平衡判断的非递归版本比中序遍历复杂不少需要同时记录每个结点的高度信息因此很少被要求当场写。我个人建议还是先把递归版本讲透再去了解栈模拟。5.4 从判断走向构造和 AVL 旋转的衔接点这道题学完下一步经常接到的追问是“如果插入一个结点后树不平衡了怎么调整”。判断函数的价值就在于帮你定位问题。你可以先用getHeightIfBalanced找到第一个返回 -1 的结点然后看它左右子树哪边更高再结合插入位置判断是 LL、RR、LR 还是 RL 四种形态选择对应的单旋或双旋。我当年是从这题开始理解 AVL 旋转的。没有想清楚“平衡”定义是什么看旋转代码就像看魔术想清楚之后旋转就成了恢复“每个结点左右高度差不超过1”的机械步骤。所以别小看这两个判断题它是通往自平衡二叉搜索树的第一级台阶。从个人经验来说这种题最忌讳的就是背代码。我见过有人把区间法背得滚瓜烂熟换一棵“所有值都是负数”的树就不会了也有人用中序法写得很顺但一被问到“为什么 prev 要传指针”就答不上来。把定义和复杂度分析吃透之后你会发现这类题变来变去核心永远是那两个词约束传递和高度复用。建议把上面的测试用例全部跑一遍再手动删掉某个判断分支看看错误输出是什么样的印象会比单纯看文章深刻得多。
第一次见到这道题是在数据结构的习题册里“判断二叉树是否为二叉排序树”“判断二叉树是否为平衡二叉树”。我当时觉得这不难左右子树比一比、高度算一算不就有答案了吗后来真正用 C 语言写代码才发现问题远比想象的细——判断二叉排序树的关键不是“当前结点和左右孩子的比较”而是祖先结点一路传下来的区间约束判断平衡二叉树也不只是算高度而是要设计一个能在后序遍历里一边返回高度、一边暴露不平衡状态的递归函数。这两个判断题是二叉树递归思想的经典应用也是很多课程设计、笔试和面试里的高频题。这篇文章把两个问题的完整思路、可运行的 C 语言代码以及我自己写题时踩过的坑逐个讲清楚适合正在备考数据结构、刷题练递归的朋友参考。1. 两个判断题里最容易被坑的定义边界很多题不是不会写而是对“二叉排序树”和“平衡二叉树”的理解停留在表面导致代码写了半天边界情况一跑就翻车。先把定义抠清楚后面所有代码才有依据。1.1 二叉排序树的“所有”两个字卡掉了多少人二叉排序树BST的经典定义是要么是空树如果左子树不空那么左子树上所有结点的值均小于根结点的值如果右子树不空那么右子树上所有结点的值均大于根结点的值同时左右子树本身也必须是二叉排序树。注意“所有”两个字。很多人写判断时只看“左孩子小于根、右孩子大于根”这个认知会留下大坑。看下面这棵树10 / \ 5 15 / \ 6 20单看每一对父子关系全是对的5 小于 1015 大于 106 小于 1520 大于 15。但整棵树不是二叉排序树因为 6 在根结点 10 的右子树里却比 10 小。也就是说“左子树所有值都小于根”是一个全局约束它会在递归向下时逐层传递一个结点不仅要比父亲大还要比所有“右转过来的祖先”大比所有“左转过来的祖先”小。这个反例我印象极深。某次课程作业里我就用“只比较父子”的写法构造了一棵类似结构的树结果程序自信地输出了“是二叉排序树”。直到老师提醒“局部有序不等于整体有序”我才意识到问题出在约束传递上。1.2 平衡二叉树空树也算平衡别漏掉基准情况平衡二叉树通常指每个结点的左右子树高度差绝对值不超过 1并且左右子树本身也平衡。它有两个容易被忽略的基准空树是平衡的单个结点也是平衡的。正因为空树算平衡判断函数的递归出口通常写成if (root NULL) return 1;并且计算高度时空树高度定义为 0。这两个约定看起来很基础但真的会有人把空树的平衡判断写成返回 0导致一棵空树被判成“不平衡”后面所有正确结果全部被带偏。还要区分一组概念完全二叉树、满二叉树、平衡二叉树。完全二叉树一定平衡但平衡树不一定是完全二叉树。比如一棵左边深度为 2、右边深度为 1 的树每个结点高度差都满足约束但它并不是教科书里那种“从左到右连续填充”的完全形态。所以判断平衡时不要拿“有没有缺结点”来脑补只看高度差。1.3 排序和平衡是两个独立维度别混为一谈二叉排序树关心的是“值的大小顺序”平衡二叉树关心的是“高度分布”。一棵二叉排序树完全可能退化成长链例如 1 → 2 → 3 → 4 这样一路向右延伸它的中序确实是递增的但它肯定不是平衡二叉树因为根结点右子树高度为 n-1左子树高度为 0差值远超 1。反过来一棵平衡树也保证不了有序。假设某个结点的左子树无论怎么填只要高度和右子树差不多它就能满足平衡约束但里面的值和根的大小关系可能完全乱掉。所以这两个判断题是两个独立函数写的时候也不要默认“一棵树如果满足 BST 就一定平衡”或“平衡就一定有序”。很多题目会把两个问题放在同一道大题里但考察点完全是两道题。2. 二叉排序树判断的正解从逐个比较到区间约束先把最流行的错误写法亮出来再给出两种正确解法。只有知道错在哪才能真正理解为什么需要区间约束。2.1 最流行的错误写法只比较父子结点很多初学者的第一版代码长这样int isBSTWrong(BiTree root) { if (root NULL) return 1; if (root-lchild root-lchild-data root-data) return 0; if (root-rchild root-rchild-data root-data) return 0; return isBSTWrong(root-lchild) isBSTWrong(root-rchild); }这段代码的问题非常隐蔽它只检查了当前结点和直接孩子的大小关系完全没有检查孙子、曾孙那一层。回到前面的反例树10、5、15、6、20这个函数会一路返回“真”因为 6 不和 10 直接比较它只和 15 比较。为什么会有这种思维惯性因为画树的时候大部分人眼睛先看“相邻两层”忽略了二叉排序树定义里强调的是“子树上的所有结点”。一个结点只要存在于某祖先的左子树里它就受这条左转路径上的所有上限约束存在于右子树里就受所有下限约束。只比较父子相当于把一条完整的约束链砍成了碎片。2.2 正确解法一递归时传递上下界区间把约束看作一个取值区间函数从根开始带着整个区间递归整棵树的初始区间是“负无穷到正无穷”。递归进入左子树时上限收紧为当前结点值因为左子树所有值都必须小于当前结点。递归进入右子树时下限收紧为当前结点值因为右子树所有值都必须大于当前结点。对应代码int isBSTByRange(BiTree root, long long min, long long max) { if (root NULL) return 1; if (root-data min || root-data max) return 0; return isBSTByRange(root-lchild, min, root-data) isBSTByRange(root-rchild, root-data, max); }调用时传入isBSTByRange(root, LLONG_MIN, LLONG_MAX);这里有一个我踩过的坑为什么边界类型用long long而不是int如果直接用INT_MIN和INT_MAX一旦树里某个结点的值恰好等于INT_MIN第一层判断root-data INT_MIN就会为真把一棵合法单结点树误判成非法。用long long并把边界设为LLONG_MIN、LLONG_MAX就能留出足够余量避免边界值误伤。如果你不想依赖long long也可以用“指针表示无界”的方案传入BiTNode *minNode和BiTNode *maxNode为NULL表示没有边界比较时先判断指针是否为NULL再比较root-data与minNode-data、maxNode-data的大小。这个方案在值范围受限的系统里更安全但写起来会多几行条件判断笔试时按个人习惯选择即可。2.3 正确解法二中序遍历严格递增二叉排序树还有一个等价性质中序遍历结果严格递增。利用这个性质可以一边递归中序遍历一边检查当前结点值是否大于上一个访问值。因为递归会跨层共享状态C 语言里必须传入一个指针变量prev来保存上一个访问值int isBSTByInorder(BiTree root, long long *prev) { if (root NULL) return 1; if (!isBSTByInorder(root-lchild, prev)) return 0; if (root-data *prev) return 0; *prev root-data; return isBSTByInorder(root-rchild, prev); }调用方式long long prev LLONG_MIN; isBSTByInorder(root, prev);为什么prev初值也用LLONG_MIN和区间法的理由一样如果树中第一个访问的结点恰好是INT_MIN用INT_MIN作为初值第一轮root-data prev就成立代码会把合法树判成非法。写成LLONG_MIN之后再和int比较编译器会做整型提升不会误伤。还要提醒一个细节递归左子树时如果已经返回 0必须立刻return 0不要在继续往右走的同时更新prev。顺序一旦乱掉可能会用一个错误的前驱值去比较右子树导致结果不可信。2.4 两种方法怎么选实际对比区间法和中序法的时间复杂度都是 O(n)区别主要在编码风格和可扩展性上。对比项区间法中序法核心思路每层递归收紧上下界中序遍历形成的序列有序额外参数min、max 两个边界一个 prev 指针边界值处理用 long long 或指针表示无界prev 初值也需要大范围类型可扩展性只能做判断可以顺便输出有序序列、找第 k 小代码量较短逻辑直观稍长但思路好理解如果题目只要求判断是否是二叉排序树我个人推荐区间法代码短、不容易写乱。如果后续还要基于中序做其他操作比如输出升序序列或查找中序第 k 个元素那中序法可以一次复用写成独立的遍历函数更顺。3. 平衡二叉树判断一次后序遍历拿捏高度O(n) 解决判断平衡树的核心难点不是递归本身而是如何避免重复计算子树高度。朴素写法能跑但复杂度不够漂亮。3.1 “先算高度再判断”的朴素写法为什么慢最常见的第一版代码如下int treeHeight(BiTree root) { if (root NULL) return 0; int l treeHeight(root-lchild); int r treeHeight(root-rchild); return (l r ? l : r) 1; } int isBalancedSlow(BiTree root) { if (root NULL) return 1; if (abs(treeHeight(root-lchild) - treeHeight(root-rchild)) 1) return 0; return isBalancedSlow(root-lchild) isBalancedSlow(root-rchild); }这个版本能正确工作但性能却是 O(n²)。原因在于isBalancedSlow对每个结点都调用一次treeHeight而treeHeight本身又会对子树的所有结点做一次遍历。一个结点既要在“判断自己在不在平衡状态”时被算高度又要在“父亲判断平衡”时被算一遍还会在“祖父判断平衡”时再被算一遍。最坏情况是一棵高度为 n 的斜树根结点调用treeHeight遍历 n 个结点第二层遍历 n-1 个结点第三层遍历 n-2 个结点累加起来是一个等差数列求和复杂度就是 O(n²)。练习时数据量小看不出问题一旦树有几万个结点递归栈和重复计算都会变得非常难受。3.2 用 -1 作为哨兵后序遍历同时返回高度优化思路其实很简单既然判断平衡需要高度那就在递归处理子树时把子树高度直接“带回来”。后序遍历左、右、根天然适合做这件事因为只有先知道左右子树的高度才能判断当前根是否平衡。函数返回值设计为返回子树高度如果发现子树不平衡则返回 -1。这样一棵子树是否平衡直接被编码进返回值里不用额外开全局变量也不用传指针进来。int getHeightIfBalanced(BiTree root) { if (root NULL) return 0; int leftH getHeightIfBalanced(root-lchild); if (leftH -1) return -1; int rightH getHeightIfBalanced(root-rchild); if (rightH -1) return -1; if (abs(leftH - rightH) 1) return -1; return (leftH rightH ? leftH : rightH) 1; }对外再包一层int isBalancedTree(BiTree root) { return getHeightIfBalanced(root) ! -1; }这里的顺序是刻意安排的先递归左子树如果左子树已经不平衡立刻返回 -1不再递归右子树。这种提前结束能省掉大量无效遍历是实际跑起来性能更好的关键。空树返回 0叶子结点返回 1完全符合高度定义。3.3 -1 这个哨兵值会不会和真实高度冲突这是一个值得展开讲的问题。二叉树高度最小是 0空树叶子结点是 1任何合法子树的高度都不可能为负数。所以用 -1 表示“不平衡”不会和真实高度混淆是安全的哨兵值。如果你在面试现场面试官可能会追问“为什么返回值不直接设计成布尔型”。可以这样回答如果只返回布尔值父结点就没有办法知道当前子树的高度必须再调用一次getHeight就会退回朴素写法的 O(n²)。而返回高度或者 -1本质上是把“平衡性”和“高度”两个信息压缩在一个整数里。如果面试官要求更语义化的写法也可以改成返回一个结构体typedef struct { int height; int balanced; } Result;每次递归返回Result代码更可读但结构体赋值和判断会多一点代码。笔试手写 C 时-1 哨兵方案最省事我个人常年在代码里写这个版本。3.4 平衡判断里最容易出现的三处低级错误第一处是忘记检查子树返回值-1。如果不做if (leftH -1) return -1;后面会拿-1去参与高度差计算结果完全失真。第二处是abs漏掉或写错高度差一定要取绝对值否则左高右低和右高左低会有一个方向永远发现不了。第三处是递归顺序写成了前序或者中序当前根还没拿到子树高度就开始比较自然拿不到正确信息。这三类错误我在帮同学排查代码时都见过每一条都值得在写完后自查一遍。4. 完整的 C 语言实现与测试用例前面把原理和关键代码都讲清楚了这一节给出一份可以直接复制运行的完整测试工程。结构体、辅助函数、三个判断函数、主函数测试用例一步到位。4.1 数据结构定义与建树辅助函数#include stdio.h #include stdlib.h #include limits.h typedef struct BiTNode { int data; struct BiTNode *lchild; struct BiTNode *rchild; } BiTNode, *BiTree; BiTree createNode(int val) { BiTree node (BiTree)malloc(sizeof(BiTNode)); node-data val; node-lchild node-rchild NULL; return node; }createNode只是一个辅助函数避免在构造测试树时反复写三行 malloc 赋值。实际工程中建树可能来自输入序列但本题的重点是判断所以直接把树结构手动搭出来最清晰。4.2 三个判断函数完整版// 区间法判断二叉排序树 int isBSTByRange(BiTree root, long long min, long long max) { if (root NULL) return 1; if (root-data min || root-data max) return 0; return isBSTByRange(root-lchild, min, root-data) isBSTByRange(root-rchild, root-data, max); } // 中序法判断二叉排序树 int isBSTByInorder(BiTree root, long long *prev) { if (root NULL) return 1; if (!isBSTByInorder(root-lchild, prev)) return 0; if (root-data *prev) return 0; *prev root-data; return isBSTByInorder(root-rchild, prev); } // 平衡二叉树判断返回 -1 表示不平衡否则返回子树高度 int getHeightIfBalanced(BiTree root) { if (root NULL) return 0; int leftH getHeightIfBalanced(root-lchild); if (leftH -1) return -1; int rightH getHeightIfBalanced(root-rchild); if (rightH -1) return -1; if (abs(leftH - rightH) 1) return -1; return (leftH rightH ? leftH : rightH) 1; } int isBalancedTree(BiTree root) { return getHeightIfBalanced(root) ! -1; }中序法调用时注意先声明long long prev LLONG_MIN;再把prev传给函数。区间法直接传LLONG_MIN和LLONG_MAX这两个宏定义在limits.h头文件里。4.3 测试用例设计每一棵树想验证什么我准备了七组测试树覆盖正常情况、反例、边界值、重复值和退化情况。编号树描述预期 BST预期平衡树1标准 BST10、5、15、2、7、12、20是是树2局部有序反例10、5、15、6、20否是树3含重复值10、10、15按无重复定义否是树4平衡且有序10、5、20、3、7是是树5有序但退化10、5、20、3、4是否树6空树是是树7单结点树是是树2是全文反复使用的反例它专门用来验证“只比较父子”的错误写法是否被识别出来。树5需要重点看一下结构10 / \ 5 20 / 3 \ 4左子树从 3 到 4 到 5 形成一条下行链高度是 3右子树高度是 1差值超过 1所以不是平衡树但中序遍历 3、4、5、10、20 严格递增所以是 BST。4.4 主函数与运行结果int main() { BiTree t1 createNode(10); t1-lchild createNode(5); t1-rchild createNode(15); t1-lchild-lchild createNode(2); t1-lchild-rchild createNode(7); t1-rchild-lchild createNode(12); t1-rchild-rchild createNode(20); BiTree t2 createNode(10); t2-lchild createNode(5); t2-rchild createNode(15); t2-rchild-lchild createNode(6); t2-rchild-rchild createNode(20); BiTree t3 createNode(10); t3-lchild createNode(10); t3-rchild createNode(15); BiTree t4 createNode(10); t4-lchild createNode(5); t4-rchild createNode(20); t4-lchild-lchild createNode(3); t4-lchild-rchild createNode(7); BiTree t5 createNode(10); t5-lchild createNode(5); t5-rchild createNode(20); t5-lchild-lchild createNode(3); t5-lchild-lchild-rchild createNode(4); BiTree t6 NULL; BiTree t7 createNode(10); BiTree trees[] {t1, t2, t3, t4, t5, t6, t7}; int i; for (i 0; i 7; i) { long long prev LLONG_MIN; int bst1 isBSTByRange(trees[i], LLONG_MIN, LLONG_MAX); int bst2 isBSTByInorder(trees[i], prev); int bal isBalancedTree(trees[i]); printf(Tree %d: RangeBST%d InorderBST%d Balanced%d\n, i 1, bst1, bst2, bal); } return 0; }运行结果如下Tree 1: RangeBST1 InorderBST1 Balanced1 Tree 2: RangeBST0 InorderBST0 Balanced1 Tree 3: RangeBST0 InorderBST0 Balanced1 Tree 4: RangeBST1 InorderBST1 Balanced1 Tree 5: RangeBST1 InorderBST1 Balanced0 Tree 6: RangeBST1 InorderBST1 Balanced1 Tree 7: RangeBST1 InorderBST1 Balanced1区间法和中序法输出的 BST 判断结果完全一致这说明两套思路在逻辑上是等价的。树6空树和树7单结点都同时通过三个判断基准情况没有被漏掉。5. 考试与面试中的变体思路重复值、空树、复杂度的追问这类题单纯跑通还不是终点面试官和考试题经常会换个语义来问或者要求你换一种实现方式。下面几个变体是我实际遇到过或者帮别人辅导时见过的高频延伸。5.1 遇到“重复值算不算 BST”怎么办这题的答案一律是“看题面定义”。没有重复值的前提下BST 要求严格小于和严格大于所以中序序列严格递增区间法边界用和判断。如果题目允许重复并采用“左子树小于等于根、右子树大于根”这类约定那么中序法要把root-data *prev改成root-data *prev区间法的左边界判断也要同步调整。最稳妥的做法是在代码注释里写明自己的假设/* 按常见无重复结点定义左小右大 */手撕代码时如果面试官没有明确说我建议直接先问一句“树里允许重复值吗”。这句话本身就能让面试官觉得你对语义敏感比默默写一个版本然后被测试用例打脸强得多。5.2 空树和单结点先确认约定再写注释不同教材对空树是不是二叉排序树的表述不完全一致但绝大多数递归定义里空树算 BST也算平衡树。如果你不放心可以在注释里写清楚按“空树合法”的约定返回真如果题目要求空树返回假把root NULL的返回值改成 0 即可。单结点也一样它既是 BST 又是平衡树。很多边界错误恰恰是在这些最“简单”的例子上翻车的测试用例一定要包含它们。5.3 如果面试官要求非递归版本递归版本的缺点是深度过大时可能栈溢出。中序遍历的 BST 判断可以改成显式栈模拟int isBSTNonRecursive(BiTree root) { BiTree stack[1024]; int top -1; long long prev LLONG_MIN; BiTree cur root; while (cur ! NULL || top ! -1) { while (cur ! NULL) { stack[top] cur; cur cur-lchild; } cur stack[top--]; if (cur-data prev) return 0; prev cur-data; cur cur-rchild; } return 1; }这段代码的思路就是把递归中序遍历改成手工压栈函数栈变成显式数组栈。空间复杂度 O(n)。如果继续追问能不能做到 O(1) 空间那就涉及线索化思想的 Morris 遍历它能利用叶子结点的空指针作为临时前驱实现常数空间的遍历但理解成本更高面试时通常作为加分项出现。平衡判断的非递归版本比中序遍历复杂不少需要同时记录每个结点的高度信息因此很少被要求当场写。我个人建议还是先把递归版本讲透再去了解栈模拟。5.4 从判断走向构造和 AVL 旋转的衔接点这道题学完下一步经常接到的追问是“如果插入一个结点后树不平衡了怎么调整”。判断函数的价值就在于帮你定位问题。你可以先用getHeightIfBalanced找到第一个返回 -1 的结点然后看它左右子树哪边更高再结合插入位置判断是 LL、RR、LR 还是 RL 四种形态选择对应的单旋或双旋。我当年是从这题开始理解 AVL 旋转的。没有想清楚“平衡”定义是什么看旋转代码就像看魔术想清楚之后旋转就成了恢复“每个结点左右高度差不超过1”的机械步骤。所以别小看这两个判断题它是通往自平衡二叉搜索树的第一级台阶。从个人经验来说这种题最忌讳的就是背代码。我见过有人把区间法背得滚瓜烂熟换一棵“所有值都是负数”的树就不会了也有人用中序法写得很顺但一被问到“为什么 prev 要传指针”就答不上来。把定义和复杂度分析吃透之后你会发现这类题变来变去核心永远是那两个词约束传递和高度复用。建议把上面的测试用例全部跑一遍再手动删掉某个判断分支看看错误输出是什么样的印象会比单纯看文章深刻得多。
