平衡二叉树判断：从 O(n²) 到 O(n) 的高效优化

平衡二叉树的定义

平衡二叉树（AVL 树）的核心在于高度平衡。空树或左右子树高度差不超过 1，且子树本身也是平衡的。

解题思路

暴力递归法（O(n²)）

直观想法是计算每个节点的高度，然后比较左右差值。但问题是，每次计算高度都要遍历整棵树，导致大量重复工作。比如根节点的高度依赖子树高度，而子树高度又依赖孙节点，这种自顶向下的方式在深层树中会反复访问同一节点。

后序遍历优化（O(n)）

利用后序遍历的特性，在返回高度的同时判断是否平衡。如果子树不平衡，直接返回 -1 标记，避免无效计算。这样每个节点只被访问一次，时间复杂度降为线性。

代码实现

先看下基础的高度和判断逻辑，这里用 Java 实现。

public boolean isBalanced(TreeNode root) {
    if (root == null) {
        return true;
    }
    int leftH = getHigh(root.left);
    int rightH = getHigh(root.right);
    return Math.abs(leftH - rightH) <= 1 && isBalanced(root.left) && isBalanced(root.right);
}

public int getHigh(TreeNode root) {
    if (root == null) {
        return 0;
    }
    int leftH = getHigh(root.left);
    int rightH = getHigh(root.right);
    return leftH > rightH ? leftH + 1 : rightH + 1;
}

上面的写法虽然逻辑通顺，但效率不高。我们来看看如何优化。

核心改动在于 getHigh 方法：它不再单纯返回高度，而是通过返回值传递平衡状态。如果某棵子树不平衡，直接返回 -1，上层调用时检测到负数即可提前终止。

public boolean  {
     (root == ) {
         ;
    }
     getHigh(root) >= ;
}

   {
     (root == ) {
         ;
    }
       getHigh(root.left);
     (leftH < ) {
         -;
    }
       getHigh(root.right);
     (leftH >=  && rightH >=  && Math.abs(leftH - rightH) <= ) {
         leftH > rightH ? leftH +  : rightH + ;
    }  {
         -;
    }
}