数据结构里有一类题特别有意思看起来简单动手写就翻车比如“用C语言判断一棵二叉树是否为二叉排序树再判断它是否为平衡二叉树”。这两道题我当年刷题时踩过不少坑后来给某高校的学生做辅导也经常看到类似的错误。二叉排序树考的是中序遍历和递归边界的理解平衡二叉树考的是子树高度的计算方式两道题放一起其实是在逼你吃透“树的递归本质”。这篇文章想把我实际跑过的代码、踩过的坑、以及一些网上很少讲清楚的细节一起整理出来给正在啃数据结构的读者一个可以直接照抄的思路。先说清楚这两道题到底在干什么。二叉排序树也叫二叉搜索树要求左子树所有节点值小于根节点右子树所有节点值大于根节点而且左右子树本身也要满足这个条件。平衡二叉树则要求每个节点的左右子树高度差的绝对值不超过1。判断前者关键是想清楚“中序遍历结果是递增序列”这条性质判断后者关键是想清楚“如何在不重复计算的情况下获取子树高度”。这篇文章既适合正在准备期末考试或考研的在校学生也适合面试前临时补数据结构基础的人。我会给出完整的C语言实现解释每一步的为什么再把容易错的地方单独拎出来讲一遍。1. 判断前的必备知识两棵特殊树的定义与推理很多同学一上来就写代码我在旁边看着都急。判断一棵树是不是二叉排序树你至少得先回答一个问题空树算不算课本上的定义一般说“空树也是二叉树”但对二叉排序树不同教材口径不一样。大多数人包括我自己在工程实践里默认空树算二叉排序树也算平衡二叉树。后面写代码就按这个口径来如果你单位有特殊要求改一下初始判断就行。1.1 二叉排序树的三条隐藏特性第一中序遍历结果是严格递增序列。这个性质是解法一的依据也是最不容易记错的一条。第二左子树所有值必须小于根节点右子树所有值必须大于根节点注意是“所有”不是“直接孩子”。很多错误代码只判断了根和左右孩子的关系遇到下面这种情况就会漏判10 / 6 \ 12根是10左孩子是66的右孩子是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 三种方法对比与复杂度梳理方法核心思路时间复杂度空间复杂度推荐场景中序序列法利用中序遍历递增性质O(n)O(h) 递归栈考试首选好记上下界递归法验证每个子树值的开区间O(n)O(h) 递归栈理解本质面试讲原理Morris遍历法线索二叉树中序O(1)空间O(n)O(1)追求极致空间的笔试我个人的建议是考试用中序序列法最稳面试讲解用上下界法显得你理解更深。二者代码我都贴出来了任选备用。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、2prev初始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上大概1MBLinux默认栈空间8MB左右每个递归帧消耗几十字节到上百字节几千层的递归就可能爆栈。如果你预判测试数据会产生很深的退化树可以考虑增大栈空间或用迭代方式实现中序遍历。不过考试时基本不会玩到爆栈这种极限工作上如果处理超大数据集要提前评估环境栈限制或者干脆用非递归栈模拟。6.7 单元测试用例设计清单我调这类树题目的习惯是准备一张测试用例表每次写完代码先拿空树、单节点、双节点、完全二叉树、退化链表树各跑一遍用例特征预期结果验证要点空树BST 平衡边界口径单节点树BST 平衡无需比较前驱左孩子大于根非BST中序递增被破坏右孩子小于根非BST中序递增被破坏左子树内部出现大值非BST只判断父子层级的漏洞高度差为2的树非平衡高度差阈值判断每个子树平衡但整体失衡非平衡必须递归到子树内部两万节点随机树运行不超时自底向上性能验证这个表既是调试工具也是我复查代码的思路清单。只要其中一项没通过优先怀疑递归边界或者比较符号不要急着改主体逻辑。回头聊聊一个实际调试案例。有一次我模拟某公司机考题要求一次遍历同时返回BST和平衡判断我一开始用了两个独立的递归函数时间复杂度倒是没超但代码显得很冗长。后来改成结构体返回三四个字段代码短了思路也更清晰。面试官问原理时我能直接把“子树信息如何向上传递”讲明白。这种改写的价值不只体现在AC上更是对递归思维的真正掌握。最后分享一个小的实用经验当你拿到一道树相关的数据结构题先别急着写代码像我前面那样在纸上画一棵小树手动模拟一遍中序遍历和高度计算把自己绕晕了再写出递归关系。树的问题本质上是递归的问题递归关系没搞清楚之前什么代码都是空中楼阁。把二叉排序树和平衡二叉树这道经典习题吃透以后很多类似的树形递归题比如判断对称树、求最大路径和、找最近公共祖先思考方式都能顺下来。
解法)
