【码道初阶】【LeetCode 110】平衡二叉树：如何用一个“Magic Number”将复杂度从O(N²)降为 O(N)？

【LeetCode 110】平衡二叉树：如何用一个“Magic Number”将复杂度降为 O(N)？

判断一棵二叉树是否是平衡二叉树（Balanced Binary Tree），是数据结构面试中的一道“分水岭”题目。

很多同学能立刻写出第一种解法，但往往会被面试官指出效率过低。如何从O(N2)O(N^2)O(N2)的暴力解法进化到O(N)O(N)O(N)的最优解法？秘密就在于如何巧妙地利用递归的返回值。

题目回顾：
给定一个二叉树，判断它是否是高度平衡的二叉树。（一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1）。

解法一：自顶向下（直观但低效）

这是最符合人类直觉的思路：既然要求“每个节点”都要平衡，那我就写一个计算高度的方法，然后挨个检查每一个节点。

1. 代码实现

classSolution{// 主函数publicbooleanisBalanced(TreeNoderoot){if(root==null)returntrue;// 1. 先计算当前节点左右子树的高度intleftTreeHeight=getHeight(root.left);intrightTreeHeight=getHeight(root.right);// 2. 核心判断（三条标准必须同时满足）：// A. 当前节点的高度差 <= 1// B. 左子树也是平衡的 (递归)// C. 右子树也是平衡的 (递归)return(Math.abs(leftTreeHeight-rightTreeHeight)<2)&&isBalanced(root.left)&&isBalanced(root.right);}// 辅助函数：纯粹计算高度publicintgetHeight(TreeNoderoot){if(root==null)return0;returnMath.max(getHeight(root.left),getHeight(root.right))+1;}}

2. 为什么它不够好？

这个解法采用了前序遍历的思想（先办事，再下放）。
它的致命伤在于重复计算：

• 在判断root是否平衡时，getHeight已经遍历了所有的子节点。
• 接着判断root.left是否平衡时，又要重新调用getHeight遍历root.left底下的子节点。
• 越底层的节点，被重复访问的次数越多。

时间复杂度：O(N2)O(N^2)O(N2)。在树退化成链表时，效率极低。

解法二：自底向上（高效的最优解）

为了消除重复计算，我们需要采用后序遍历的思想：
不要总是上级向下级问话，而是让下级把结果汇报上来。

如果某个子树发现自己不平衡了，它不应该只是简单地返回高度，而是应该返回一个错误信号（Magic Number），比如-1。父节点一旦收到-1，就知道下面出事了，直接停止计算，继续向上报错。

1. 代码实现

classSolution{publicbooleanisBalanced(TreeNoderoot){// 如果 getHeight 返回 -1，说明这棵树是不平衡的returngetHeight(root)>=0;}// 修改后的 getHeight：既返回高度，又兼职“报警”// 约定：如果不平衡，返回 -1；如果平衡，返回实际高度publicintgetHeight(TreeNoderoot){if(root==null)return0;// 1. 先算左边intleftHeight=getHeight(root.left);// 【剪枝】如果左边已经出事了（返回-1），那我也直接报错，不往下走了if(leftHeight<0){return-1;}// 2. 再算右边intrightHeight=getHeight(root.right);// 【剪枝】如果右边出事了，或者我自己左右差 > 1，都报错if(rightHeight<0||Math.abs(leftHeight-rightHeight)>1){return-1;}else{// 3. 一切正常，汇报真实高度returnMath.max(leftHeight,rightHeight)+1;}}}

2. 核心难点图解：-1 是如何产生和传递的？

很多初学者卡在leftHeight < 0这个判断上。到底谁产生了-1？谁又接收了-1？
我们通过一个具体的不平衡树来模拟全过程：

1 <-- 根节点 / \ 2 3 / 4 / 5

(注：节点 2 的左树高度为 2，右树为 0，差值为 2，不平衡)

代码执行流程模拟：

第一阶段：深入底层

程序递归直到最底部的节点 5。

• getHeight(5)：左右为空，返回高度1。

第二阶段：向上汇报

回到节点 4。

• getHeight(4)：左边收到 1，右边是 0。高度差 1。正常，返回高度2。

第三阶段：始作俑者（错误产生的源头）

回到节点 2。

• 它调用getHeight(4)，变量leftHeight拿到值2。
• 它调用getHeight(null)，变量rightHeight拿到值0。
• 关键判断：Math.abs(2 - 0) > 1成立！
• 动作：节点 2 发现自己不平衡，于是触发return -1;。

  注意：这里是-1第一次被制造出来的地方。

第四阶段：传声筒（错误的传递）

回到根节点 1。

• 它执行第一行代码：int leftHeight = getHeight(root.left);（即访问节点 2）。
• 接收：因为节点 2 返回了-1，所以变量leftHeight现在等于-1。
• 剪枝：

  if(leftHeight<0){return-1;}

  条件成立！根节点 1 甚至不需要去计算右子树（节点 3）的高度，直接向外抛出-1。

3. 公司职级比喻

如果把这棵树比作公司：

• 节点 2（底层经理）：发现部门出了大问题（不平衡），于是向上级汇报代码-1（而不是业绩）。
• 节点 1（总经理）：收到下属汇报的-1，立刻明白出事了，于是停止计算公司总业绩，直接向董事会也汇报-1。
• isBalanced（董事会）：看到最终结果是-1，判定结果为false。

总结与对比

最终结论：
解法二通过引入-1作为状态标记，巧妙地将“计算高度”和“检测平衡”融合在了一次遍历中，实现了时间复杂度的降维打击。掌握这种“利用返回值携带额外信息”的技巧，是解决二叉树问题的核心能力之一。