判断平衡二叉树的详解（Java 实现）

平衡二叉树的定义：
平衡二叉树（Balanced Binary Tree）是指一棵二叉树中任意节点的左右子树高度差不超过 1。即：
$$|height(left)-height(right)|\le 1$$
且其左右子树也是平衡二叉树。

---

实现步骤

1. 高度计算：通过递归方式计算每个节点的高度。
2. 平衡性判断：递归判断每个节点是否满足高度差小于等于 1 的条件。

---

方法 1：自顶向下递归（不优化）

1. 计算节点高度：从底部开始递归求节点高度。
2. 判断平衡性：对每个节点，检查左右子树的高度差是否满足条件。

代码实现：

class TreeNode {
    
      
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int val) {
    
      
        this.val = val;
    }
}

public class BalancedBinaryTree {
    
      
    // 判断是否为平衡二叉树
    public 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);
    }

    // 计算树的高度
    private int height(TreeNode node) {
    
      
        if (node == null) return 0; // 空节点高度为 0
        return Math.max(height(node.left), height(node.right)) + 1;
    }
}

分析：

• 时间复杂度： 每个节点调用一次 height，height 递归访问所有子节点，因此时间复杂度为 $O(n^2)$。
• 空间复杂度： 递归栈空间取决于树的高度，最差情况下为 $O(n)$（链式树）。

---

方法 2：自底向上递归（优化版）

改进思路：

• 在一次递归中同时计算高度和判断平衡性。
• 如果某个子树不平衡，直接返回，避免重复计算。

代码实现：

public class BalancedBinaryTree {
    
      
    // 判断是否为平衡二叉树
    public boolean isBalanced(TreeNode root) {
    
      
        return checkHeight(root) != -1; // 如果返回 -1，表示不平衡
    }

    // 递归检查平衡性，同时返回高度
    private int checkHeight(TreeNode node) {
    
      
        if (node == null) return 0; // 空节点高度为 0

        // 检查左子树是否平衡
        int leftHeight = checkHeight(node.left);
        if (leftHeight == -1) return -1; // 左子树不平衡，直接返回

        // 检查右子树是否平衡
        int rightHeight = checkHeight(node.right);
        if (rightHeight == -1) return -1; // 右子树不平衡，直接返回

        // 判断当前节点是否平衡
        if (Math.abs(leftHeight - rightHeight) > 1) return -1;

        // 返回当前节点的高度
        return Math.max(leftHeight, rightHeight) + 1;
    }
}

分析：

• 时间复杂度： 每个节点只访问一次，时间复杂度为 $O(n)$。
• 空间复杂度： 递归栈空间取决于树的高度，最差情况下为 $O(n)$（链式树）。

---

测试代码

public class Main {
    
      
    public static void main(String[] args) {
    
      
        // 构造一个平衡二叉树
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(2);
        root.left.left = new TreeNode(3);
        root.left.right = new TreeNode(3);
        root.left.left.left = new TreeNode(4);
        root.left.left.right = new TreeNode(4);

        BalancedBinaryTree tree = new BalancedBinaryTree();
        System.out.println(tree.isBalanced(root)); // 输出 false（该树不平衡）
    }
}

---

总结

1. 方法 1：自顶向下递归
   • 简单易懂，适用于小型树。
   • 时间复杂度较高，为 $O(n^2)$。
2. 方法 2：自底向上递归
   • 高效，适用于大型树。
   • 时间复杂度为 $O(n)$。

选择方法 2 是更优的方案，尤其是在树较大的情况下。