刷二叉树题碰到判断平衡基本绕不开这题。某在线判题平台的110题要求一句话就能说清楚一棵二叉树的每个节点左右子树的高度差都不能超过1。看起来只是“求高度”加“比较大小”的组合但真正动手写的时候很多人卡在“到底该返回什么”上——返回高度平衡状态怎么带出来返回布尔值又怎么知道左右子树差了多高这道题最值得琢磨的地方就在这。你可以把它当成一个递归入门的进阶题适合已经写完二叉树前中后序遍历、想搞明白递归返回值怎么设计的人也适合准备面试想在最短时间内把树的常见考点串一遍的人。今天这篇会把从暴力思路到O(n)实现完整拆开包括我踩过的几个坑希望能帮你彻底绕开这些弯路。尤其是“返回高度还是返回布尔值”这个选择很多教程直接给了代码却没有解释为什么这次我会把原因讲透。1. 题目理解与思路拆解1.1 平衡二叉树到底在考什么先明确定义。平衡二叉树要求的是任意节点的左右子树高度差绝对值不超过1注意是“任意节点”不是只检查根节点也不是要求整棵树所有叶子在同一层。比如一个完全平衡的满二叉树当然是平衡的但左右子树高度只相差1的树也是平衡的这是初学者容易混淆的地方。题目真正想考的是你能不能把一个看似需要“遍历所有节点、每个节点再算高度”的问题用递归清晰表达出来。这个题在面试里出现频率高是因为它不依赖复杂的算法纯粹考察递归分解。树的问题大多数都能拆成“当前节点做什么 子节点交给递归”而平衡判断又天然依赖子树的信息要知道当前节点是否平衡必须先知道左右子树的高度要知道左右子树高度又得从更下层往上汇总。这种自下而上的信息流动正好对应二叉树的后序遍历顺序。换句话说这题不是单纯考“你知不知道什么是平衡”而是考“你能不能把递归调用当成一个可以携带返回信息的黑盒来设计”。实际工程里平衡判断也不只是学术概念。文件目录树、组织架构、表达式树、路由表这类树形结构一旦某一侧疯狂退化查找和修改的复杂度就会直线上升。判断一棵树是否平衡相当于给树做一次“健康体检”看看它在结构上有没有出现严重的偏科。所以把这道题理解透后面看AVL树、红黑树这类自平衡结构的时候思路会顺很多。1.2 为什么先算高度再谈平衡要判断平衡就得先知道高度。这里先约定一种常见的计算口径空节点的高度记为0叶子节点高度记为1一个节点的高度等于它左右子树高度的最大值加1。比如一个只有根节点的树左右孩子都是空高度就是0加1等于1。这种口径在刷题时最常用因为判空直接返回0逻辑干净。有的教材会把叶子高度记为0那空节点就要返回-1两种口径都能得到正确答案关键是全代码统一别混着用。算高度这件事天然就是后序遍历。递归函数先自问左孩子的高度再自问右孩子的高度最后拿两者中较大的那个加1返回。你可以把这个过程类比成项目汇报底层员工先把自己的工作量统计好一级一级往上汇总每一层的领导只管拿到两个下属的数字做一次比较再把自己的统计结果继续向上报。从根节点出发的请求实际上要落到最底层真正的结果却是一层一层传回来的。判断平衡需要的信息恰好也是这两个数字左子树高度和右子树高度。于是很自然地会产生一个想法——能不能在同一个递归过程中又算高度又做判断这就是这题最精彩的地方。朴素做法是写两个递归一个getHeight专门算高度一个isBalanced递归检查每个节点但既然求高度时已经摸清了子树底部的情况我们完全可以顺手把平衡判断一并做了避免同一个节点的信息被反复打探。想明白这一点你就能理解为什么网上高赞题解都长得差不多因为最优解本来就是在后序遍历里塞进一个“平衡状态哨兵”。2. 两种核心解法拆解2.1 自顶向下直观但重复计算最容易想到的思路自顶向下先把定义翻译成代码。对当前节点调用一个getHeight方法算出左子树高度和右子树高度做差判断然后再递归检查当前节点的左孩子和右孩子是否各自平衡。这种解法代码写起来很符合直觉isBalanced里先处理当前节点再处理子树读起来就像在朗读题目定义。class Solution { public boolean isBalanced(TreeNode root) { if (root null) { return true; } int left getHeight(root.left); int right getHeight(root.right); return Math.abs(left - right) 1 isBalanced(root.left) isBalanced(root.right); } private int getHeight(TreeNode node) { if (node null) { return 0; } return Math.max(getHeight(node.left), getHeight(node.right)) 1; } }这个方案确实能通过测试我当年也是这么写出来的。但它有一个很扎眼的性能问题重复计算。getHeight会被反复调用同一个节点的高度可能在递归检查每个祖先时都被重新算一遍。最极端的例子是一棵退化成链表的树根节点层的getHeight会一路数到最底下然后轮到左孩子时又把剩余链数一遍所有节点被访问的次数加起来是平方级别的。就算是一棵比较工整的树这种重复也相当可观。你可以这样理解浪费在哪里节点就像是公司里一名普通员工底层晨会已经汇报过自己的绩效结果每到上面一层都要重新再汇报一次一路被领导翻来覆去地问“你下属的下属到底干得怎么样”。数据量小的时候无所谓数据量一上来这棵树的“汇报成本”就会失控。所以在面试里给出这个答案只能算及格分面试官大概率会追问一句“还能不能再优化”2.2 自底向上一次遍历完成判断优化的方向很明确把从下往上收集的信息在下一次向上传递时直接带上。具体做法是重新设计getHeight的返回值——不只在正常时返回高度还在发现子树不平衡时返回一个特殊哨兵值比如-1。因为所有节点高度都是非负整数-1不会和合法高度混淆于是这个函数就同时承担了“算高度”和“报故障”两件事。判断逻辑也变成一次完整但精简的后序遍历。递归先处理左子树如果左子树内部就不平衡函数直接返回-1当前节点连右子树都不用再访问了右子树同理。左右都没问题之后再看左右高度差是否超过1一旦超过也返回-1。如果这些都扛住了说明当前节点本身平衡于是正常返回左右最大高度加1。最终isBalanced只需要判断根节点返回的数值是否等于-1。class Solution { public boolean isBalanced(TreeNode root) { return height(root) ! -1; } private int height(TreeNode node) { if (node null) { return 0; } int left height(node.left); if (left -1) { return -1; } int right height(node.right); if (right -1) { return -1; } if (Math.abs(left - right) 1) { return -1; } return Math.max(left, right) 1; } }这个写法的时间复杂度是O(n)因为每个节点最多被访问一次。空间复杂度取决于递归栈深度最坏情况下是链状树的O(n)平均情况下是O(logn)。不止如此它在不平衡出现时还有提前终止的效果一旦某个子树被判定为不平衡路径上所有祖先都会立刻向上传递-1不会再浪费时间去检查这棵树的旁支。我对这个设计的评价是高度和平衡状态合二为一返回值契约清晰剪枝又自然几乎没有废动作。对比维度自顶向下自底向上遍历次数同一节点可能被多次访问每个节点最多访问一次最坏时间复杂度O(n^2)O(n)空间复杂度递归栈O(h)递归栈O(h)代码直观度和定义一致容易上手需要理解哨兵值面试评价能过但容易被追问优化思路完整加分项3. 完整实现与代码走读3.1 自底向上的参考实现上面已经给出了Java版本的核心代码这里再逐行拆一遍因为很多新手看完答案以为懂了真到自己写又容易在几个细节上翻车。第一个细节height方法在node为null时返回0这是递归的出口也是“空子树高度为0”这一约定的落地。第二个细节先递归左子树马上检查left是否等于-1是就立即返回。这里先处理左后处理右的顺序本身不重要但“拿到结果立刻检查”的习惯很重要它保证了剪枝能够及时生效。第三个细节左右子树都检查完再用Math.abs(left - right) 1判断当前节点是否平衡。有人写代码时容易在返回条件里漏掉绝对值只比较left right 1这样会漏判右子树比左子树高的情况。第四个细节也是最容易被忽略的返回的是Math.max(left, right) 1不是left 1或right 1。当前节点的高度取决于更高的那个孩子这是树的定义写错的话整个高度体系都会乱掉。这个方法对外暴露的接口只有一个isBalanced内部用height返回-1来表示“我已经发现不平衡了”。整体边界非常清晰空树返回true因为height(null)等于0不等于-1单节点返回true因为左右都为空差值为0。面试时如果考官要求你讲思路我建议先讲自顶向下版本再顺势说“存在重复访问的问题”然后给出这个自底向上的版本这样既展示了基础能力又展示了优化意识。这里补充一点如果使用“叶子高度为0、空节点高度为-1”的约定代码的出口、高度加1逻辑、平衡判断条件都要跟着调整。我个人不推荐在刷题时用那套口径因为空节点返回-1会让很多人在递归出口处迷茫。你只要选定一套口径写之前用注释在函数头部写明“返回值含义”基本就不会错。3.2 边界条件与典型用例写代码之前最好先在脑子里过一遍边界用例最经典的几个包括空树、单节点、满二叉树、左右高度只差1的树、单侧链状树。空树和单节点是递归出口层面最好理解的两个都平衡。满二叉树每个节点的左右子树高度完全一致当然平衡。高度差刚好等于1的树比如根节点左子树有三层右子树有两层但每个子树内部也都符合条件这种树依然是平衡的因为定义容忍1的差值。真正容易翻车的是单侧链状树比如所有节点都只有左孩子这样一个“左偏树”。从根节点开始每个节点都会发现左子树高度比右子树高并且最终某个节点的左右高度差会超过1于是-1一路向上返回整棵树被判定为不平衡。这种用例特别适合用来验证你的剪枝逻辑有没有写对正常情况下递归到倒数第二层的时候就该触发不平衡的返回条件了而不是老老实实遍历完整条链。我为自查整理过一张用例速查表每次写完这种递归题目都会套一遍这样可以快速筛出低级错误输入树预期结果原因空树true空节点高度为0无节点需要检查单节点true左右子树高度均为0差值为0满二叉树深度3true所有节点左右子树高度相等根节点左子树深度2、右子树深度3true高度差为1左右子树内部也平衡左偏链表深度4false沿左链越往下左右高度差越大根节点左右子树高度相同但左子树内部不平衡false子树不平衡会通过-1向上传播构造测试树的时候我的习惯是先画一张小图标清每个节点的高度再手动走一遍递归。不要一开始就丢一个很大的随机树进去跑那样即使程序跑错了也很难定位问题是出在“平衡判断”还是“高度计算”。人脑模拟递归栈虽然费时间但对理解后序传播这件事帮助极大值得在入门阶段多练几次。4. 常见问题与排查技巧实录4.1 只判断根节点是否平衡的误区我见过最多的一种错误是把题目理解成“只要根节点的左右子树高度差不超过1即可”。在这个思路下有人会写出下面这种逻辑算出整个左子树高度和整个右子树高度发现差不多直接返回true完全没有递归去检查左孩子和右孩子内部的情况。这样的代码在绝大多数简单用例上都能通过一遇到“根节点平衡但子树不平衡”的组合就会翻车。举个具体的反例结构根节点的左子树和右子树都是三层高表面看起来差值为0很平衡但左子树的根节点下面左孩子还有两层右孩子却是空也就是左子树内部本身就是不平衡的。按照题目定义整棵树必须判false可只看根节点的代码会返回true。这种例子完美地说明了“平衡是针对每一个节点的属性不是只针对树根”。排查这类问题最直接的方式就是在每个节点上打印左右子树高度和当前差值观察看看到底是哪个节点开始不满足条件的。如果发现自己打印出来的差值列表里有某个子树内部的高度差大于1那就说明你的递归漏了下层检查。修复的方法就是回到正道上要么在递归里检查孩子要么采用自底向上的哨兵写法让下层问题直接通过返回值暴露。4.2 递归返回值设计混乱第二个常见问题是返回值的含义想不清楚代码写出来自己都晕。最典型的情况是isBalanced方法返回布尔值里面却又调用另一个getHeight去算高度导致两个函数职责交叉代码里到处都是“高度”和“是否平衡”两套数据的搬运。这种写法不是不行但很容易在边界问题上绕进去尤其是一旦涉及递归每一次调用都得同时处理两件事心智负担明显变大。我之前在给朋友讲题时看到有人写过这样一个版本height函数里发现不平衡时返回0然后把0和“空树高度0”混在一起导致上层无法区分“这里空了”和“这里不平衡了”。这就是明显的哨兵值污染。正确做法是选一个不可能在正常逻辑里出现的值作为特殊标记比如-1并在注释里写明返回值大于等于0表示高度等于-1表示子树不合法。这样函数调用者只需要做一次判等不需要猜语义。如果你发现自己总在递归里迷路我提供一个实操习惯动手写代码前先写一段文字注释说清楚这个函数输入和输出之间契约是什么。比如“height(node)在一棵没有异常的子树中返回其高度如果某一子树不平衡直接返回-1并停止后续计算。”把注释写明白写代码时就不容易自相矛盾。还有一个小建议不要在同一个文件里同时保留两套高度工具函数临时调试可以提交前一定要清理否则后面维护的人会在两个函数之间反复摇摆。4.3 重复计算带来的性能陷阱自顶向下版虽然简单性能问题却很隐蔽。我用一个计数器实际测过在一棵10层的完全二叉树上自顶向下版本的getHeight被调用的次数远多于节点总数而自底向上版本基本稳定在节点总数级别。数据量再大一点自顶向下能明显感觉到延迟。面试的时候如果你先说了自顶向下接着意识到重复计算并提出优化这是一个很自然的加分过程但如果只给出暴力版本又没有意识到问题可能就需要等考官提醒才能继续。定位重复计算的调试技巧也很简单。在getHeight入口加一行日志输出当前节点的值然后输入一棵只有几层的小树跑完自顶向下版再跑一遍自底向上版对比输出行数。你会立刻看到前者存在大量重复后者每个节点几乎只出现一次。这个方法比看时间复杂度分析更直观因为实际日志会直接打脸“好像也没有多算几次”的错觉。如果你的思路是“给getHeight加上一个哈希表缓存把算过的高度存起来”这种优化方向也能降低时间复杂度但代价是额外空间和更复杂的代码面试时不如自底向上的思路优雅。缓存方法适用于“被迫使用自顶向下逻辑”的场景而本题没有这个限制所以直接通过返回值传递信息才是更扎实的答案。我的建议是一旦发现同一棵树被递归函数反复扫描优先思考能不能把计算挪到遍历过程中顺便完成而不是急着加缓存。5. 延伸思考与应用场景5.1 从平衡判断到AVL树这道题做透之后再看AVL树会轻松不少。AVL是最早的自平衡二叉搜索树之一它对每个节点都维护一个“平衡因子”也就是左子树高度减右子树高度的值。AVL要求这个因子的绝对值不超过1这不就是110题判断的平衡条件吗当插入或删除节点导致某个节点的平衡因子变成2或-2时AVL会通过旋转操作重新恢复平衡而旋转之前要搞清楚哪棵子树更高、高了多少这些信息都来自高度计算。如果希望往算法深处再走一步我建议刷完这题后立刻练几个同类的后序返回题目验证二叉搜索树、求二叉树直径、二叉树中的最大路径和。它们的共性都是“子树返回值里携带多个信息”比如直径那道题既要返回当前子树的高度给父节点用又要维护一个全局变量记录经过当前节点的最长路径。这种把“给上层的东西”和“自己在意的结果”分开处理的模式在树形动态规划里反复出现。很多人在AVL知识上只停留在“听说过旋转”的层面因为没把基础的高度判断吃透。实际上旋转的四个情况归根到底都是某一边偏高而判断“偏高”的根据正是平衡因子。你如果把110题的哨兵值写法理解透了再去看AVL的插入修复流程会发现代码里的每次旋转前都有一个高度差判断的步骤和刷题时的判断逻辑同源。先打牢底层的判断力再看上层实现整个知识链条就通顺了。5.2 实际工程里的用武之地不要觉得树平衡只是面试考点真实系统里也经常需要这个判断。文件目录如果一层层套得很深路径搜索会变慢组织架构树如果不平衡审批链会异常冗长表达式树如果一边倒求值时间复杂度会退化。在这些场景下写一个“检查树是否平衡”的小工具可以作为系统性能体检的一部分提前发现结构性问题。有时候我甚至会在测试环境里用同样的递归思路去检查某个配置树是否因为手工修改变成了畸形结构。进一步想这题还能引出一些更深的讨论。比如树特别大内存里放不下怎么办你可以把树序列化后按需加载再用同样的递归思路逐段判断比如允许对节点做预处理缓存你可以在节点对象里保存自己的height字段这样判定平衡的时间能降到近乎O(1)。这些都属于优化扩展面试中如果聊得深入能体现你对数据结构工具化的理解而不只是停留在“刷过题”的层面。最后分享一个我调这类递归题的小习惯先写一个只负责求高度的函数验证无误后再把它升级成带哨兵值的写法。升级的时候不要直接删旧代码而是另开一个计数器分别统计自顶向下和自底向上访问节点的次数你会直观看到那行“left -1 return -1”省下了多少递归。我的体会是二叉树的递归题难的地方往往不在递归本身而在返回值的设计。110题把这个点拿捏得特别准想清楚之后后面很多树的题目都会顺很多。