判断平衡二叉树

在这里插入图片描述所谓平衡二叉树，就是任意节点的左右子树高度差不超过1。

话不多说，看几个例子帮助理解:

✅ 平衡的树:

每个节点的左右子树高度差都 ≤ 1

❌ 不平衡的树:

节点1的左子树高度为2,右子树高度为0,差值为2 > 1

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27


public static boolean balance;

public static boolean isBalanced(TreeNode root) {
    // 每次调用都重置全局标志
    balance = true;
    height(root);
    return balance;
}

public static int height(TreeNode cur) {
    // 剪枝:一旦发现不平衡,或遇到空节点,直接返回
    if (!balance || cur == null) {
       return 0;
    }
    
    // 递归计算左右子树高度
    int lh = height(cur.left);
    int rh = height(cur.right);
    
    // 检查当前节点是否平衡
    if (Math.abs(lh - rh) > 1) {
       balance = false;
    }
    
    // 返回当前节点的高度
    return Math.max(lh, rh) + 1;
}

如果觉得有帮助，欢迎点赞、关注、转发~