降为 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。 - 剪枝：
条件成立！根节点 1 甚至不需要去计算右子树（节点 3）的高度，直接向外抛出if(leftHeight<0){return-1;}-1。
3. 公司职级比喻
如果把这棵树比作公司：
- 节点 2（底层经理）：发现部门出了大问题（不平衡），于是向上级汇报代码
-1（而不是业绩）。 - 节点 1（总经理）：收到下属汇报的
-1，立刻明白出事了，于是停止计算公司总业绩，直接向董事会也汇报-1。 - isBalanced（董事会）：看到最终结果是
-1，判定结果为false。
总结与对比
| 维度 | 解法一（自顶向下） | 解法二（自底向上） |
|---|---|---|
| 遍历思想 | 前序 (Preorder) | 后序 (Postorder) |
| 核心操作 | 计算高度与判断逻辑分离 | 计算高度的同时判断平衡 |
| 时间复杂度 | O(N2)O(N^2)O(N2)(最差情况) | O(N)O(N)O(N)(最优) |
| 效率 | 低 (大量重复计算子节点高度) | 高 (每个节点只访问一次) |
| 返回值含义 | 仅代表是否平衡 (Boolean) | 既代表高度，又用 -1 代表不平衡 |
最终结论：
解法二通过引入-1作为状态标记，巧妙地将“计算高度”和“检测平衡”融合在了一次遍历中，实现了时间复杂度的降维打击。掌握这种“利用返回值携带额外信息”的技巧，是解决二叉树问题的核心能力之一。
