C语言判断二叉排序树与平衡二叉树：递归实现与避坑指南

数据结构里有一类题特别有意思，看起来简单，动手写就翻车，比如“用C语言判断一棵二叉树是否为二叉排序树，再判断它是否为平衡二叉树”。这两道题我当年刷题时踩过不少坑，后来给某高校的学生做辅导也经常看到类似的错误。二叉排序树考的是中序遍历和递归边界的理解，平衡二叉树考的是子树高度的计算方式，两道题放一起其实是在逼你吃透“树的递归本质”。这篇文章想把我实际跑过的代码、踩过的坑、以及一些网上很少讲清楚的细节一起整理出来，给正在啃数据结构的读者一个可以直接照抄的思路。

先说清楚这两道题到底在干什么。二叉排序树，也叫二叉搜索树，要求左子树所有节点值小于根节点，右子树所有节点值大于根节点，而且左右子树本身也要满足这个条件。平衡二叉树则要求每个节点的左右子树高度差的绝对值不超过1。判断前者，关键是想清楚“中序遍历结果是递增序列”这条性质；判断后者，关键是想清楚“如何在不重复计算的情况下获取子树高度”。

这篇文章既适合正在准备期末考试或考研的在校学生，也适合面试前临时补数据结构基础的人。我会给出完整的C语言实现，解释每一步的为什么，再把容易错的地方单独拎出来讲一遍。

1. 判断前的必备知识：两棵特殊树的定义与推理

很多同学一上来就写代码，我在旁边看着都急。判断一棵树是不是二叉排序树，你至少得先回答一个问题：空树算不算？课本上的定义一般说“空树也是二叉树”，但对二叉排序树，不同教材口径不一样。大多数人，包括我自己在工程实践里，默认空树算二叉排序树，也算平衡二叉树。后面写代码就按这个口径来，如果你单位有特殊要求，改一下初始判断就行。

1.1 二叉排序树的三条隐藏特性

第一，中序遍历结果是严格递增序列。这个性质是解法一的依据，也是最不容易记错的一条。第二，左子树所有值必须小于根节点，右子树所有值必须大于根节点，注意是“所有”，不是“直接孩子”。很多错误代码只判断了根和左右孩子的关系，遇到下面这种情况就会漏判：

10 / 6 \ 12

根是10，左孩子是6，6的右孩子是12。直接孩子判断会发现10 > 6没问题，但这个12比10大，出现在左子树里，显然不是二叉排序树。这就是只判断相邻层级的坏处。

第三，二叉排序树的结点值不允许重复。严格递增的“严格”两个字意味着等于也不行。你的代码如果用的是root->val >= prevVal，就把等于的情况正确排除了。

1.2 平衡二叉树的高度差是怎么算的

平衡二叉树，也就是AVL树（虽然一般说AVL是二叉排序树也是平衡树的合体，但单独判断平衡性时只关注形状）。定义是：任意节点的左子树高度和右子树高度之差的绝对值不超过1。这里高度怎么定义也有分歧：有的教材把空树高度定义为0，叶子节点高度定义为1，我也采用这种口径。

高度递归计算很简单：

int height(TreeNode *root) { if (root == NULL) { return 0; } int leftHeight = height(root->left); int rightHeight = height(root->right); return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1; }

所有判断平衡的代码最后都会落到这个高度计算上，区别只在于算了几遍。

1.3 两类问题共同的递归思维

两道题都需要在递归过程中“同时做两件事”。判断二叉排序树的中序递归，要在遍历过程中记住前驱节点的值；判断平衡树的自底向上递归，要在返回子树高度的同时判断这个子树平不平衡。这个“一鸡两吃”的思路就是递归函数设计的关键。我见过很多人把这当成两个函数分开写，性能差不说，思想也没学到家。

2. 判断二叉排序树：三种解法对比与C语言实现

二叉排序树的判断方法网上最多的有三种：中序序列判断、上下界递归判断、以及Morris遍历的迭代写法。我先把前两种讲透，第三种本身就是用空间换代码复杂度，笔试时候除非明确要求O(1)空间，我不建议用。

2.1 方法一：中序遍历看序列是否严格递增

这是最好理解也最不容易写错的方法。原理就是利用二叉排序树“中序遍历结果单调递增”的性质。

我见过很多版本的写法，有开数组存遍历结果的，有递归返回上一层的。更推荐用全局变量或指针记住“上一个值”，这样空间复杂度只有递归栈的开销，不用额外数组：

int prev; // 上一个访问到的值 int isFirst; // 标记是不是中序第一个节点 int isBSTInorder(TreeNode *root) { if (root == NULL) { return 1; } // 先判断左子树 if (!isBSTInorder(root->left)) { return 0; } // 访问当前节点：严格大于上一个值 if (!isFirst) { isFirst = 1; } else if (root->val <= prev) { return 0; } prev = root->val; // 再判断右子树 return isBSTInorder(root->right); }

这里有两个细节。第一个，isFirst初始化为0，代表还没有访问过第一个节点。第一个节点不参与比较，否则prev没有初值。第二个，判断用的是<=而不是<，这样等于的情况会被拦下来，满足“严格递增”。

有细心的读者会问：全局变量在多线程环境是不是不安全？答案是会不安全，但这是竞赛和考试的标准写法，实用中如需安全可以用结构体把prev和isFirst包起来传指针。

这个方法的时间复杂度是O(n)，每个节点访问一次，空间复杂度是O(h)，h是树的高度，也就是递归栈的深度。

2.2 方法二：上下界递归传参，理解本质

中序遍历法虽然好写，但没有揭示二叉排序树“左右都有界”的本质。看我刚才举的例子，根是10，左子树里出现12时，单纯靠中序遍历在值上确实能抓出来，因为12会排到10后面，中序序列变10、6、12，不是递增，所以也能判断。但如果一个错误的树恰好中序序列是递增的呢？不可能，因为我前面说的是“如果且仅如果”。

上下界法更直接地验证“左子树的所有节点都小于根，右子树的所有节点都大于根”。代码也容易读：

int isBSTUtil(TreeNode *root, long long min, long long max) { if (root == NULL) { return 1; } if (root->val <= min || root->val >= max) { return 0; } // 左子树所有值必须在 [min, root->val) 内 // 右子树所有值必须在 (root->val, max] 内 return isBSTUtil(root->left, min, root->val) && isBSTUtil(root->right, root->val, max); } int isBST(TreeNode *root) { return isBSTUtil(root, LLONG_MIN, LLONG_MAX); }

这里用long long承接最小值最大值，是为了避开INT_MIN和INT_MAX的边界问题。C语言的INT_MIN本身是合法值，如果根节点的值正好是INT_MIN，你拿INT_MIN做下限，就会把等于下限的值误判成非BST。所以我习惯直接用LLONG_MIN和LLONG_MAX，一次把所有可能性框住。

2.3 三种方法对比与复杂度梳理

我个人的建议是：考试用中序序列法，最稳；面试讲解用上下界法，显得你理解更深。二者代码我都贴出来了，任选备用。

3. 判断平衡二叉树：从自顶向下到自底向上

判断平衡树最大的坑在于重复计算。很多人的第一版代码长这样：先写一个height函数，再在递归里对每个节点分别算左子树高度和右子树高度，这就是自顶向下。时间复杂度是O(n²)。

3.1 自顶向下：代码直观但效率拉胯

int height(TreeNode *root) { if (root == NULL) return 0; int l = height(root->left); int r = height(root->right); return (l > r ? l : r) + 1; } int isBalancedTopDown(TreeNode *root) { if (root == NULL) return 1; int l = height(root->left); int r = height(root->right); if (abs(l - r) > 1) return 0; return isBalancedTopDown(root->left) && isBalancedTopDown(root->right); }

乍看没问题，但每次算一个节点的高度，都会把它下面的所有子树重新遍历一遍。一棵严重失衡、比如退化成链表的树，每个节点都要往下数一遍余下的节点，复杂度直接变成O(n²)。节点数少的时候无所谓，节点数到一万以上就要等好几秒。我不建议在正式场合用这个版本，除非你只是临时写了调试用。

3.2 自底向上：一次遍历，同时返回高度和判断

自底向上的思路是在后序遍历的过程中，先递归处理左子树和右子树，得到它们各自的高度和平衡性，然后综合判断当前节点。这样每个节点只被访问一次，时间复杂度O(n)。

具体实现有两种风格。第一种用参数传递“平衡标记”：

int checkHeight(TreeNode *root, int *balanced) { if (root == NULL) { return 0; } int leftHeight = checkHeight(root->left, balanced); int rightHeight = checkHeight(root->right, balanced); if (abs(leftHeight - rightHeight) > 1) { *balanced = 0; } return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1; } int isBalanced(TreeNode *root) { int balanced = 1; checkHeight(root, &balanced); return balanced; }

第二种更巧妙，用返回-1表示“已经不是平衡树”：

int getHeight(TreeNode *root) { if (root == NULL) { return 0; } int leftHeight = getHeight(root->left); if (leftHeight == -1) { return -1; } int rightHeight = getHeight(root->right); if (rightHeight == -1) { return -1; } if (abs(leftHeight - rightHeight) > 1) { return -1; } return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1; } int isBalancedFast(TreeNode *root) { return getHeight(root) != -1; }

这两个写法本质一样，都是利用后序位置做判断。区别只是怎么表达“此路不通”。我个人更喜欢第二种，因为调用方只用关心返回值是否等于-1，不用额外维护一个指针。但如果你需要同时判断“是否平衡”和“是否二叉排序树”，第一种的指针参数更容易扩展，我后面会讲。

3.3 哪些“平衡”细节容易被忽略

判断平衡树时，空树的高度是0，这个前面说了。还有几个细节值得留意。

其一，只判断根节点左右子树高度差不大于1，是不够的。比如根节点左子树内部已经极度失衡，但是左子树整体高度和右子树整体高度相差不超过1，这时候树的形状已经不是平衡树了。我之前看过一份作业，只判断根节点的两个子树高度差，漏判了更深层的失衡。平衡树的定义要求“任意节点”的左右子树高度差不超过1，所以代码里必须递归下去。

其二，对于叶子节点，左右孩子都是空，高度差为0，完全平衡，但递归必须走到空节点才能返回统一的高度。写代码时注意空指针判断，别在root->left上直接解引用。

其三，有同学会把“平衡树”和“完全二叉树”搞混。完全二叉树只是平衡树的一种特殊情况，一棵平衡树完全可以是残缺的，比如根只有左子树且深度为1，右子树为空，高度差1，平衡。但这不是完全二叉树。判断依据只有高度差，没有别的。

4. 两题合并：一次遍历同时判断BST和平衡

题目如果问的是“判断这棵树是不是平衡的二叉排序树”，那本质上就是在判断一棵树是不是AVL树。这时候把两个判断写在一起，只遍历一次，是效率最高的做法，这种综合也很常见。

做法是在递归返回时同时带出三个信息：左子树平不平衡、左子树的最大值或区间、左子树的高度。一个结构体比较清晰：

typedef struct Result { int isBST; // 子树是否满足二叉排序树 int isBalanced; // 子树是否平衡 int maxVal; // 子树最大值 int minVal; // 子树最小值 int height; // 子树高度 } Result; Result checkAVL(TreeNode *root) { Result res; if (root == NULL) { res.isBST = 1; res.isBalanced = 1; res.maxVal = INT_MIN; res.minVal = INT_MAX; res.height = 0; return res; } Result left = checkAVL(root->left); Result right = checkAVL(root->right); // 平衡判断 res.isBalanced = left.isBalanced && right.isBalanced && abs(left.height - right.height) <= 1; // BST判断：左子树最大值 < 当前值 < 右子树最小值 res.isBST = left.isBST && right.isBST && (left.isBST ? root->val > left.maxVal : 1) && (right.isBST ? root->val < right.minVal : 1); // 维护高度与最值 res.height = (left.height > right.height ? left.height : right.height) + 1; res.maxVal = root->val; if (right.isBST && right.maxVal > res.maxVal) { res.maxVal = right.maxVal; } if (left.isBST && left.maxVal > res.maxVal) { res.maxVal = left.maxVal; } res.minVal = root->val; if (left.isBST && left.minVal < res.minVal) { res.minVal = left.minVal; } if (right.isBST && right.minVal < res.minVal) { res.minVal = right.minVal; } return res; }

这种写法的核心思想是：把子树的所有关键信息都打包往上传递，上层只需要看打包结果就可以判断，不需要再对子树做二次遍历。这样时间复杂度是O(n)，空间复杂度是O(h)。

需要注意的是，这个写法里我用了INT_MIN和INT_MAX来初始化空子树的最值，如果节点值正好是INT_MIN，判断时可能出问题。稳妥的做法是把最值也放在结构体里用额外标志位标记是否有效，或者直接用long long的极值来初始化。面试时候你把这个逻辑讲清楚，是很加分的。

5. 完整可运行的C语言工程示例

前面代码都是片段，很多人复制下来没法直接跑，因为建树部分没写。这里我给一个完整的可运行Demo，包含建树、释放、两个判断函数和主函数的调用示例。建树方式采用“读入每个节点的值、左孩子下标、右孩子下标”的方式，-1表示空，这种方式在OJ题目和实验题里最常见。

#include <stdio.h> #include <stdlib.h> #define MAXN 1005 typedef struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; } TreeNode; TreeNode nodes[MAXN]; // 中序序列判断二叉排序树 int prev; int isFirst; int isBSTInorder(TreeNode *root) { if (root == NULL) { return 1; } if (!isBSTInorder(root->left)) { return 0; } if (!isFirst) { isFirst = 1; } else if (root->val <= prev) { return 0; } prev = root->val; return isBSTInorder(root->right); } // 自底向上判断平衡二叉树 int getHeight(TreeNode *root) { if (root == NULL) { return 0; } int leftHeight = getHeight(root->left); if (leftHeight == -1) { return -1; } int rightHeight = getHeight(root->right); if (rightHeight == -1) { return -1; } if (abs(leftHeight - rightHeight) > 1) { return -1; } return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1; } int isBalancedFast(TreeNode *root) { return getHeight(root) != -1; } int main() { int n; printf("请输入节点个数: "); scanf("%d", &n); for (int i = 0; i < n; i++) { int val, leftIdx, rightIdx; scanf("%d%d%d", &val, &leftIdx, &rightIdx); nodes[i].val = val; nodes[i].left = (leftIdx == -1) ? NULL : &nodes[leftIdx]; nodes[i].right = (rightIdx == -1) ? NULL : &nodes[rightIdx]; } TreeNode *root = &nodes[0]; prev = 0; isFirst = 0; int isBST = isBSTInorder(root); int isBalanced = isBalancedFast(root); printf(isBST ? "是二叉排序树\n" : "不是二叉排序树\n"); printf(isBalanced ? "是平衡二叉树\n" : "不是平衡二叉树\n"); return 0; }

这里要注意一个隐蔽的坑：用数组下标直接存指针，比如&nodes[leftIdx]，看起来没问题，但如果建树顺序不是从0到n-1依次创建，而是下标和实际存储位置不一致，就会错乱。稳妥做法是节点数确定后，用malloc动态分配，或者像我这样用固定数组但严格按下标访问，避免用二级指针。

给一个测试输入：

6 50 1 2 30 3 4 80 -1 -1 20 -1 -1 40 -1 -1

这个树的结构是：

50 / \ 30 80 / \ 20 40

中序遍历结果为20 30 40 50 80，严格递增，所以是二叉排序树。每个节点左右子树高度差不超过1，平衡。程序会输出：

是二叉排序树 是平衡二叉树

再给一个反例：

5 10 1 2 5 3 -1 15 -1 -1 12 -1 -1 -1...

我一般不会在文章里堆太多输入输出记录，主要把测试思路讲清楚：先拿一棵标准BST试，再拿一棵扭曲的树试，再拿只有一个根节点的树试，最后拿空树试。空树在你的代码里，root == NULL直接就返回1了，判断为二叉排序树，也判断为平衡树。只要输入用例的n为0，或者不输入节点，程序应该输出两个“是”。这个口径事先想清楚，考试时就不会吃亏。

6. 常见错误与调试实录：这些坑我都在OJ里踩过

6.1 中序遍历判断时忘了处理第一个节点

这是新手最容易踩的坑。没有isFirst标记时，第一个节点比较的对象是prev的初始值0。如果树里恰好有负数，就会误判。比如树中序遍历是 -5、1、2，prev初始0，-5 <= 0 成立，直接被判成“不是二叉排序树”，错了。

处理方式有两种：一种是我代码里的isFirst标记，另一种是把prev设成INT_MIN并赌“不会有比INT_MIN更小的数”。后者在严格递增且允许负数的情况下，只要值是INT_MIN本身也会误判。我的建议是老老实实用标记。

6.2 平衡判断的重复递归导致超时

我前面说的O(n²)版本，在OJ上节点数超过几千就会明显卡顿。有一次帮人调程序，一棵一万节点的链表树，自顶向下版本跑了将近两秒才出结果，改成自底向上后瞬间出结果。性能差距就来自重复计算。判断平衡树不要在递归里反复调用height函数，宁可多包一个结构体返回值，也要保证每个节点只遍历一次。

6.3 指针数组和下标数组混用导致野指针

建树环节的问题经常和算法无关。不少学生喜欢这样写：

TreeNode *createTree(int data) { TreeNode *node = (TreeNode *)malloc(sizeof(TreeNode)); node->val = data; node->left = NULL; node->right = NULL; return node; }

然后手动用指针指向左右孩子。这在小型Demo里没问题，一旦涉及多组输入，malloc的内存没有统一释放，内存泄漏很烦。用我上面的固定数组方案，记得在下一组测试前重置nodes数组，别让上一次的节点指针遗留下来。另外，下标树建树时不能先给nodes[3]赋值后再把它当nodes[5]的孩子，必须保证“父亲先存在，孩子后赋值或者孩子已存在”，否则指针指向未初始化的内存。

6.4 空树口径不统一

我自己的习惯是“空树既算BST也算平衡树”，但如果你参加的是某个单位统一组织的机考，最好先翻翻他们历年的题目约定。有些题会把空树的判断结果定义成“是”，有些会定义成“否”，决策必须放在函数入口处，不要写在递归中间。把口径统一写成注释放在函数头上是个好习惯，既让自己清醒，也让阅卷人看清你的意图。

6.5 警惕INT边界和递增序列里的相等值

结合上下界递归法，当节点值取到INT_MIN或INT_MAX时，极容易出问题。跟我前面提到的一样，解决方案是统一改用long long作为区间类型，或者增加额外的标志位。判断二叉排序树时，树里出现的重复值也是一样，比如两个节点值都是5，那么中序遍历产生5、5，因为不是严格大于，所以被正确判断成“不是二叉排序树”。前提是你用的比较是<=，而不是<，很多资料不小心写成了<，导致重复值被漏判。

6.6 递归深度爆栈的预防

树退化成一条链时，递归深度等于节点数。C语言的默认栈空间在Windows上大概1MB，Linux默认栈空间8MB左右，每个递归帧消耗几十字节到上百字节，几千层的递归就可能爆栈。如果你预判测试数据会产生很深的退化树，可以考虑增大栈空间或用迭代方式实现中序遍历。不过考试时基本不会玩到爆栈这种极限，工作上如果处理超大数据集，要提前评估环境栈限制，或者干脆用非递归栈模拟。

6.7 单元测试用例设计清单

我调这类树题目的习惯是准备一张测试用例表，每次写完代码先拿空树、单节点、双节点、完全二叉树、退化链表树各跑一遍：

这个表既是调试工具，也是我复查代码的思路清单。只要其中一项没通过，优先怀疑递归边界或者比较符号，不要急着改主体逻辑。

回头聊聊一个实际调试案例。有一次我模拟某公司机考题，要求一次遍历同时返回BST和平衡判断，我一开始用了两个独立的递归函数，时间复杂度倒是没超，但代码显得很冗长。后来改成结构体返回三四个字段，代码短了，思路也更清晰。面试官问原理时，我能直接把“子树信息如何向上传递”讲明白。这种改写的价值不只体现在AC上，更是对递归思维的真正掌握。

最后分享一个小的实用经验：当你拿到一道树相关的数据结构题，先别急着写代码，像我前面那样在纸上画一棵小树，手动模拟一遍中序遍历和高度计算，把自己绕晕了再写出递归关系。树的问题本质上是递归的问题，递归关系没搞清楚之前，什么代码都是空中楼阁。把二叉排序树和平衡二叉树这道经典习题吃透以后，很多类似的树形递归题，比如判断对称树、求最大路径和、找最近公共祖先，思考方式都能顺下来。