如何判断一棵二叉树是否是平衡二叉树？

简化版

平衡二叉树的定义是：每个节点的左右子树高度差都不超过 1。朴素做法对每个节点算一次左右子树高度再比较，但会重复计算、O(n²)。最优解用后序遍历自底向上：递归时同时返回「子树高度」，一旦发现某棵子树不平衡就用特殊值（如 -1）向上传递，提前剪枝，做到 O(n)。

详细版

平衡的定义（这里指高度平衡）：任意节点的 |左子树高度 − 右子树高度| ≤ 1，且左右子树也都平衡。

最优解：后序 + 剪枝（O(n)）

boolean isBalanced(TreeNode root) {
    return height(root) != -1;
}
// 返回子树高度；若已不平衡，返回 -1 作为标记
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;       // 平衡，返回真实高度
}

思路：一个函数同时干两件事——算高度、判平衡。用返回值 -1 当「不平衡」的信号，一旦某处出现 -1 就一路往上传，避免继续计算。

完整版教学

一、朴素解法为什么是 O(n²)

最直接的想法：写一个 height() 求高度，再对每个节点判断「左右高度差是否 ≤ 1」，并递归判断左右子树是否平衡：

boolean isBalanced(TreeNode root) {
    if (root == null) return true;
    return Math.abs(height(root.left) - height(root.right)) <= 1
        && isBalanced(root.left) && isBalanced(root.right);
}

问题在于：height() 本身要遍历子树，而 isBalanced 对每个节点都调一次 height。顶层节点的 height 会把整棵树走一遍，它的孩子又各走一遍…… 高度信息被反复重算，总复杂度退化到 O(n²)（类似「每个节点都做一次 O(n) 的高度计算」）。

二、优化关键：一次遍历同时算高度和判平衡

重复计算的根源是「求高度」和「判平衡」分成了两趟。优化思路是合二为一：用一次后序遍历，在返回子树高度的同时就把「是否平衡」判掉。

后序（左右根）保证先拿到左右子树的高度，才处理当前节点——正好是「自底向上」。
用返回值兼任两职：正常返回高度；一旦不平衡，返回 -1 作为哨兵值。

这样每个节点只被访问一次，O(n)。

三、-1 剪枝的妙处

用 -1 表示「这棵子树已经不平衡」有两个好处：

提前终止：一旦左子树返回 -1，就不必再算右子树、直接把 -1 传上去，省掉后续计算。
信息复用：正常情况下返回的高度值可以直接被父节点使用，不用重新求。

这是「在递归返回值里携带额外信息，避免重复遍历」的经典技巧，在树形题里非常常见（求直径、最大路径和都用类似手法）。

四、注意「平衡」的定义

本题的「平衡」指高度平衡：每个节点左右子树高度差 ≤ 1。
它比「完全二叉树」宽松，也不同于「AVL 树 / 红黑树」这类自平衡搜索树（那些是在插入删除时通过旋转主动维持平衡，属于平衡树板块的内容）。
这里只是判断一棵给定的树是否满足高度平衡，不涉及如何维护平衡。

五、复杂度

朴素法：O(n²)，高度被反复计算。
后序剪枝法：O(n) 时间（每节点一次），O(h) 递归栈空间。

面试要能说出「朴素为什么 O(n²)」并给出 O(n) 的优化，这是本题的考点。

六、常见误区与追问

问法	面试官想确认的点
为什么用后序？	先拿到左右子树高度，当前节点才能判断平衡
为什么返回 -1？	用一个哨兵值同时表达「不平衡」和「停止继续算」
空树高度怎么算？	通常记为 0，叶子节点高度就是 1

记忆钩子：平衡判断不是只看根节点，而是每个节点都要过一遍；后序遍历正好让「子树是否平衡」先于「当前节点是否平衡」被确认。

误区：只比较根节点左右高度差就能判断平衡。 根节点平衡只能说明第一层没问题，左右子树内部仍可能已经不平衡，必须递归检查每个节点。
误区：先算完整高度再判断一定也是 O(n)。 如果每个节点都重新调用 height 扫描子树，节点会被反复访问，最坏会退化到 O(n²)。
误区：-1 是高度的一种合法结果。 这里空树高度从 0 开始，真实高度不会为负数，所以 -1 才能安全作为「已经不平衡」的哨兵。
追问：为什么不用前序遍历？ 前序先处理当前节点，但此时还不知道左右子树高度；后序先处理左右子树，天然适合自底向上传高度。
追问：递归栈空间是多少？ 空间复杂度是 O(h)，h 是树高；平衡树约 O(log n)，退化成链表时是 O(n)。
追问：这和 AVL 树有什么区别？ 本题只判断给定树是否高度平衡；AVL 是一种搜索树，会在插入删除时通过旋转主动维护平衡。

七、加强记忆

平衡二叉树 = 每个节点左右子树高度差 ≤ 1。朴素法「求高度 + 判平衡」分两趟、重复计算，O(n²)。最优解用后序遍历自底向上，一个函数同时返回高度、并用 -1 作为不平衡哨兵提前剪枝，一次遍历 O(n)。这是「递归返回值携带额外信息」的经典技巧。注意这只是判断，不同于 AVL/红黑树的主动维持平衡。

简化版

详细版