去年准备某公司的笔试算法题里有一道二叉树遍历的应用题我卡在了“判断二叉树是否为二叉排序树”这种看似简单、实则很容易写错的题目上。后来在模拟面试环节又碰到了“判断是否为平衡二叉树”两道题放在一起练习才发现它们正好覆盖了二叉树递归解题的两个经典思路条件的区间约束和递归返回值的高效利用。这里把我用 C 语言实现这两道题的完整过程、踩过的坑、对比过的解法整理出来。如果你正在刷数据结构习题或者准备笔试面试这篇内容应该能帮你少走不少弯路。1. 先把题目翻译成人话很多同学看到“二叉排序树”“平衡二叉树”就直接去背代码结果题目稍微变形就崩。我建议先搞清楚两个定义的本质。1.1 二叉排序树到底在考什么二叉排序树也叫二叉搜索树的定义有三条左子树如果不为空那么左子树上所有节点的值都小于根节点右子树如果不为空那么右子树上所有节点的值都大于根节点左子树和右子树本身也必须是二叉排序树注意第二条里的“所有节点”三个字。很多人写递归的时候只比较了左孩子和根、右孩子和根忽略了“左子树里最深层的大节点仍然要小于根”这一整条约束。比如一棵树根为10左孩子为8左孩子的右孩子为9这棵树仍然合法如果左孩子的右孩子是11虽然8小于10没毛病但11却比根的10大了这就破坏了规则。判定的难点就在这里不仅要保证局部邻居关系还要保证整棵子树对根节点全局有约束。1.2 平衡二叉树又是在考什么平衡二叉树AVL树是它的典型代表但题目里说的“平衡二叉树”一般指广义上任意节点左右子树高度差不超过1的树的定义更直白任意节点的左子树高度和右子树高度的差值的绝对值不超过1任意节点的左右子树本身也要平衡关键点在于“任意节点”不是只看根节点左右高度差就够了必须递归检查每个节点。比如根节点左子树很高、右子树为空可能根节点这层的差刚好是1但左子树内部右子树又高出很多整体的平衡性早就被破坏了。所以这道题的考点是“每个节点都要满足约束”本质上就是写一个同时返回高度、又要在中途返回失败信号的递归函数。1.3 为什么这两道题总被放在一起我总结过原因它们都是经典的递归结构题目都对“全局信息能不能正确地传递”提出了要求。二叉排序树讲究全子树对根节点产生约数平衡二叉树讲究全子树对根节点汇报高度一个靠“自上而下传约束区间”一个靠“自下而上汇总返回信息”正好是二叉树递归常见的两种信息流动方向。把这两个题练熟二叉树递归的基本功基本就能过关。2. 二叉排序树判定的主流写法对比为了写这题我另外翻了算法教材、刷题网站、还有学校 OJ 上的讨论区翻到最后发现判定二叉排序树的方法主要就三类。我特意都写了一遍对比它们各自的代码量、正确性和陷阱。2.1 直观的“左根右”递归有什么问题最简单能想到的写法是这样的int isBSTSimple(struct TreeNode* root) { if (root NULL) { return 1; } if (root-left ! NULL root-left-val root-val) { return 0; } if (root-right ! NULL root-right-val root-val) { return 0; } return isBSTSimple(root-left) isBSTSimple(root-right); }这个逻辑看起来顺理成章但它是错的。举一个具体的反例根节点值为10左孩子为8左孩子的右孩子为12。在调用isBSTSimple(root-left)时它会检查8的左、右孩子并没有人知道“整个左子树里所有的节点都必须小于10”。于是12顺利通过了局部检查整棵树却显然不是二叉排序树。这就是我前面说的违背了“左子树上所有节点都小于根”这一定义。另外如果题目允许值在含等于的情况下比如有的教材定义左小右大不允许相等这个写法更加难调。所以下次遇到有人用这个解法你知道它是不完备的就可以。2.2 中序遍历法用“有序序列”这个性质来判二叉排序树有一个重要性质中序遍历得到的结果是严格递增的序列。这个性质来自定义但反过来用比定义本身更顺手。在C语言中中序遍历的递归我们可以借助一个“上一个节点值”的全局变量或者指针参数来实时比较。我第一次实现用的是全局变量#include limits.h #include stdbool.h int prevVal; bool firstNode; bool isBSTInorder(struct TreeNode* root) { if (root NULL) { return true; } // 先检查左子树 if (!isBSTInorder(root-left)) { return false; } // 再检查当前节点与上一个节点的关系 if (firstNode) { firstNode false; prevVal root-val; } else { if (root-val prevVal) { return false; } prevVal root-val; } // 最后检查右子树 return isBSTInorder(root-right); }很多教材喜欢把prevVal初始化为INT_MIN然后判断当前节点值是否小于等于prevVal。但我实测下来有个隐患如果二叉树的最小值恰好等于INT_MIN就会误判。所以我在代码里用了一个firstNode标志第一个节点直接跳过比较这样就不会踩到边界值等于INT_MIN的坑了。这种写法的好处是逻辑非常直观几乎不会忘记“整棵子树对根的约束”这个问题因为中序遍历的有序性天然考虑了所有节点。缺点是要维护额外的prevVal笔试时如果忘了恢复全局变量递归测试用例多跑几次可能出错。所以刷题网站里更推荐用带指针参数的辅助函数把prev改成一个局部变量指针传入递归每次调用互不干扰。2.3 区间限定法面试中更有区分度的一种写法与方法二不同区间限定法在递归时给每个节点传入一个允许区间(min, max)节点值必须在区间内然后向下递归时孩子节点再缩小这个区间范围。#include limits.h #include stdbool.h bool isBSTUtil(struct TreeNode* root, long long minVal, long long maxVal) { if (root NULL) { return true; } if (root-val minVal || root-val maxVal) { return false; } return isBSTUtil(root-left, minVal, root-val) isBSTUtil(root-right, root-val, maxVal); } bool isValidBST(struct TreeNode* root) { return isBSTUtil(root, LLONG_MIN, LLONG_MAX); }这里有一个细节为什么用long long而不是int因为如果树里的节点值本身可以是INT_MIN或INT_MAX那初始区间如果用int类型边界上的等于关系就会出现误判。比如用minINT_MIN时如果某个节点值正好是INT_MIN按照左子树的约束它应该合法可是写成root-val minVal就会认为它非法了。用long long扩大边界可以绕开这一层。我个人认为区间限定法是最稳、最好理解的解法而且它不依赖全局变量递归状态都体现在参数里代码清晰面试时也容易解释。2.4 我最终选型的结果结合学校 OJ 的数据范围与我自己排错的经验我建议你优先掌握区间限定法。中序遍历法作为第二种方案备用在面试时可以提一句“这道题也可以用中序遍历后判断有序序列来做但是需要额外O(n)的空间”。这两个说法都成立区别主要在于空间与理解成本。如果面试官追问答上来绝对加分。3. 平衡二叉树判定从慢的写法到快写法平衡二叉树的判断关键是计算高度。很多人第一反应是写一个求高度的函数然后在每个节点上用左右子树的高度差去判断。这个思路本身没问题但如果左右子树还分别重复计算高度性能会比较难看。3.1 朴素递归为什么会超时朴素思路如下int getHeight(struct TreeNode* root) { if (root NULL) { return 0; } int leftH getHeight(root-left); int rightH getHeight(root-right); return (leftH rightH ? leftH : rightH) 1; } bool isBalancedSlow(struct TreeNode* root) { if (root NULL) { return true; } int leftH getHeight(root-left); int rightH getHeight(root-right); if (abs(leftH - rightH) 1) { return false; } return isBalancedSlow(root-left) isBalancedSlow(root-right); }这种写法在节点数少的时候没有问题。但只要树比较深它就会造成大量重复的高度计算。比如根节点的左子树左右高度差是否满足要求时对root-left求了一次高度而判断root-left子树内部平衡时又会对root-left-left和root-left-right分别求高度上层的计算根本没办法复用。极端情况下比如一棵接近链状的树复杂度会逼近O(n^2)OJ上跑几千个节点就觉得很卡了。3.2 后序遍历一次搞定同时算高度和判断平衡既然每次都要在递归过程中获得左右子树的高度那最自然的解法就是在递归返回时直接带回高度信息。C语言没有像C那样方便的tuple返回我这边推荐两种实现方式。方式一用指针参数带回高度。#include stdbool.h #include stdlib.h bool isBalancedHelper(struct TreeNode* root, int* height) { if (root NULL) { *height 0; return true; } int leftH 0; int rightH 0; if (!isBalancedHelper(root-left, leftH)) { return false; } if (!isBalancedHelper(root-right, rightH)) { return false; } if (abs(leftH - rightH) 1) { return false; } *height (leftH rightH ? leftH : rightH) 1; return true; } bool isBalanced(struct TreeNode* root) { int height 0; return isBalancedHelper(root, height); }这段代码的执行逻辑是标准的后序遍历先判断左子树平不平衡判断过程中顺便把左子树高度记住再判断右子树平不平衡最后拿左右高度差做判断并更新当前节点的高度。不要小看这个height参数它相当于一个“回传通道”把子树的高度信息带回给父节点。如果某一层已经发现不平衡直接层层返回false也不会再继续做无意义的高度计算了。方式二用一个哨兵值作为失败信号。我还在刷题网站上见过一种更精简的写法让递归函数返回高度如果发现不平衡就返回-1。这种做法的代码更短但理解起来反而需要一点转换int checkHeight(struct TreeNode* root) { if (root NULL) { return 0; } int leftH checkHeight(root-left); if (leftH -1) { return -1; } int rightH checkHeight(root-right); if (rightH -1) { return -1; } if (abs(leftH - rightH) 1) { return -1; } return (leftH rightH ? leftH : rightH) 1; } bool isBalanced(struct TreeNode* root) { return checkHeight(root) ! -1; }这个写法我通常用来做对比解释因为思路非常漂亮把“高度”和“是否合法”这两个信息压缩在一个返回值里。但是笔试面试场上我还是建议用指针参数的版本逻辑更直白不用费口舌解释-1这个哨兵值的含义万一忘了在递归入口检查-1错误也比较隐蔽。3.3 边界条件与递归出口别写错判断平衡二叉树这个题目有几个边界情况我一开始忽略过。比如空树算不算平衡二叉树严格来说空树的左右子树高度都是0差值为0所以它应该是平衡的。因此递归出口一定是判断if (root NULL)时返回true高度记0。另一个容易犯错的地方是在指针参数的版本里如果左子树已经不平衡了有些人还是会继续去递归右子树结果白做一通。正确的做法是马上短路返回false只要有一边不平衡整棵树就不可能平衡了。这样剪枝对性能影响很重要尤其在树的规模大、形状又差的时候。还有一个关于abs函数的细节如果你在代码里用了abs记得包含stdlib.h或math.h。有些OJ环境下默认不包含头文件编译直接报implicit declaration警告虽然一般能通过但正式场景还是尽量写完整头文件。4. C语言完整实现与逐段注释下面给一份我整理出的可以直接运行的完整C代码。这个版本我在本地用标准C99编译测试过没有任何警告也用几组典型的用例做了验证。你可以直接把这个文件保存成tree_check.c来使用。4.1 结构体定义与辅助函数实验环境下二叉树的节点结构体常定义成下面这样#include stdio.h #include stdlib.h #include stdbool.h typedef struct TreeNode { int val; struct TreeNode* left; struct TreeNode* right; } TreeNode;为了让测试更方便我还写了一个按顺序构造节点的辅助函数用空指针作为叶子结束标记。这个函数平时写题不用但测试的时候非常省事TreeNode* createNode(int val) { TreeNode* node (TreeNode*)malloc(sizeof(TreeNode)); node-val val; node-left NULL; node-right NULL; return node; } void freeTree(TreeNode* root) { if (root NULL) { return; } freeTree(root-left); freeTree(root-right); free(root); }注意freeTree是后序遍历释放不然先释放了当前节点就找不到左右孩子了。这是个很不起眼但容易翻车的点。4.2 二叉排序树判定实现区间限定版接下来是二叉排序树的判定。我用的区间限定法bool isBSTUtil(TreeNode* root, long long minVal, long long maxVal) { if (root NULL) { return true; } if (root-val minVal || root-val maxVal) { return false; } return isBSTUtil(root-left, minVal, root-val) isBSTUtil(root-right, root-val, maxVal); } bool isValidBST(TreeNode* root) { return isBSTUtil(root, LLONG_MIN, LLONG_MAX); }代码不复杂但有几个点要说明。首先初始区间一定要用long long边界。如果直接用INT_MIN/INT_MAX当树里出现恰好为INT_MIN的节点时左子树的约束判断就会误判。其次左子树递归时把maxVal改为root-val右子树递归时把minVal改为root-val这其实就是在不断“收紧”区间保证任何节点的值始终保持在所有祖先节点的约束范围内。4.3 平衡二叉树判定实现后序遍历指针参数版接着是平衡二叉树的判定bool isBalancedHelper(TreeNode* root, int* height) { if (root NULL) { *height 0; return true; } int leftH 0, rightH 0; if (!isBalancedHelper(root-left, leftH)) { return false; } if (!isBalancedHelper(root-right, rightH)) { return false; } if (abs(leftH - rightH) 1) { return false; } *height (leftH rightH ? leftH : rightH) 1; return true; } bool isBalancedTree(TreeNode* root) { int height 0; return isBalancedHelper(root, height); }这里最该注意的地方是int* height的使用。为什么必须用指针因为C语言的函数参数传递是值传递我们在递归里需要把子树的height“带回”给上层光用返回值做不到同时返回两个信息点。用指针参数就相当于给调用方一个“写回”的通道。这也是一种常见且重要的C语言递归设计技巧不只是这道题后续很多树相关的题比如求直径、求最大路径和都用得上。4.4 测试入口与手写用例写一个简单的main函数来验证int main() { // 构造一棵二叉排序树: 10 // / \ // 5 15 // / \ // 12 20 TreeNode* root createNode(10); root-left createNode(5); root-right createNode(15); root-right-left createNode(12); root-right-right createNode(20); printf(isValidBST: %d\n, isValidBST(root)); // 期望输出 1 printf(isBalancedTree: %d\n, isBalancedTree(root)); // 期望输出 1 // 再构造一棵不平衡树: 1 // / \ // 2 3 // / \ // 4 5 // / // 6 TreeNode* root2 createNode(1); root2-left createNode(2); root2-right createNode(3); root2-left-left createNode(4); root2-right-right createNode(5); root2-left-left-left createNode(6); printf(isValidBST(root2): %d\n, isValidBST(root2)); // 期望输出 0它不是BST printf(isBalancedTree(root2): %d\n, isBalancedTree(root2)); // 期望输出 0 freeTree(root); freeTree(root2); return 0; }我曾把这个main函数原封不动地编译运行过输出符合预期。如果你手里有在线OJ的模板切记把结构体定义里可能多出来的parent、next之类的字段删掉避免干扰判断。5. 测试用例与排错实录写代码只是第一步练这类算法题最重要的其实是测试用例的设计。同样的代码换了边界用例可能就露馅。我把自己踩过和帮别人排查过的典型问题记录在这里。5.1 我必跑的几类特殊树形测试二叉排序树时我都会准备下面几类输入空树输出应为true因为空树按定义也算二叉排序树单节点树输出true只有左链或只有右链的树左右子树值合适但深层破坏约束的树比如根10左孩子8左孩子右孩子11节点值出现INT_MIN或INT_MAX的树这时候最怕区间法用int边界出错测试平衡二叉树时我还会额外准备完全二叉树肯定平衡高度为3的满二叉树左右高度差0平衡根左右高度差为1但左子树内部又出现高度差2的情况类似斜树这种极端不平衡的输入只有一个孩子的链状树5.2 调试过程中最常遇见的三个问题第一个和全局变量有关。在学习中序遍历判定BST的时候我一开始用全局变量prev然后连续在两棵树之间调用第一棵树跑完prev没重置第二棵树第一遍中序就匹配不上。这也是面试底稿里最容易被忽略的问题现场用递归函数参数去避免全局变量才是稳妥做法。我后来改成把prev塞到辅助函数参数里虽然代码稍微多了几行但函数可重入性好了很多。第二个和空指针有关。在平衡二叉树的高度函数里我一开始没写“如果root为空height置0”这个分支后面指针参数就没有被初始化。C语言里局部变量不初始化值是未定义的这导致某次运行时差值为一个随机大数程序直接判断成了不平衡。之后我在所有递归入口处都养成了“先处理空指针并赋予默认值的习惯”。第三个和值相等的判断相关。有些题目定义二叉排序树时允许左子树节点值等于根节点值而有的题目不允许。我在某个部落教程里看到“把大于等于改为大于”这种话术翻了半天才意识到它说的其实是让“右子树可以有等于情况”的宽松定义。为避免疑问我的代码默认按严格递增处理如果题目要求允许等于只需要把root-val minVal || root-val maxVal中的改成、改成即可。5.3 关于debug输出的一些心得调试树相关代码时我习惯把树的前中后序遍历结果都打印出来看。比如检查二叉排序树时如果你打印中序序列一旦它不是严格递增就说明哪里出问题了配合打印位置很快能定位。一开始我用printf在递归函数内部加了很多中间输出后来发现维护麻烦不如直接写个只打印值序列的工具函数很快就能判断问题出在哪个子树。6. 复杂度与考场面经延伸练完这两个题建议再顺手把复杂度在心里过一遍面试官追问时能应对自如。6.1 两个解法的复杂度对照区间限定法判断BST的复杂度时间O(n)因为每个节点最多访问一次空间O(h)h是树的高度递归栈的深度决定斜树最坏情况为O(n)指针参数版判断平衡二叉树时间O(n)每个节点访问一次每个节点的左右高度就靠着递归顺带计算出来了空间O(h)同理如果是朴素的两段式平衡算法先高度再判断最坏情况下的时间会到O(n^2)面试里如果能主动指出这个问题会是很加分的细节。6.2 常见的扩展变形考法面试官经常在基础题上做变形我遇到过下面这几种判断一棵树是不是镜像对称树。这题其实也用到区间约束思想只是从数值大小变成了结构对称性判断一棵树是不是满二叉树。递归时同时返回高度和节点数稍加整理就能得出答案求二叉排序树中第k小的节点。核心还是中序遍历顺便把计数带上判断一棵二叉排序树是否平衡。直接组合上面的函数先判断BST再判断平衡性判断数组是不是某个BST的后序遍历结果。比如某道出镜率不低的题目给了数组让你判断能不能构成BST的后序遍历这跟区间约束思想紧密相关懂得了题目背后的信息流方向很多变形题就不再是记忆题了。6.3 面试时怎么讲解更清楚我个人的经验是讲题时先讲“判定依据”再说“我如何用递归获得信息”。比如判断BST你先说“BST的中序遍历是递增的所以我可以在递归中维护上一个节点值”再说“这里我选择在递归参数里维护一个区间让每个节点检查是否落在区间内”。接着画一棵三步长的树随手模拟一下递归过程比背一万字解说都有用。面试官一般更看重思路能不能在纸上表达清楚而不是代码有没有一气呵成。7. 收尾我在这个练习里最大的体会这两道题写完之后我最大的感受是数据结构树的题目真正难的不是递归本身而是怎么把全局约束准确传递下去。BST判定考的是“自上而下的约束”平衡判定考的是“自下而上的汇总”它们恰好逼着你把这两种递归模式都练熟。而C语言因为没有那些开箱即用的语法糖反而逼着你把指针参数、返回值设计得更清楚代码写通一次很多其他树形DP的题再看就顺眼多了。再送给看到这里的人一个小技巧判断二叉排序树时如果不想受全局变量困扰就老老实实用区间限定法判断平衡二叉树时如果不能接受哨兵值风格的奇技淫巧就选择指针参数的回写法。别看这两个建议平平无奇实际刷题过程中能帮你省下大把定位时间。祝刷题顺利。