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

平衡二叉树的定义是:它是一个空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。

我们可以使用递归的方式判断一棵二叉树是否平衡:

public boolean isBalanced(TreeNode root) {
    if (root == null) return true;
    int leftHeight = height(root.left);
    int rightHeight = height(root.right);
    if (Math.abs(leftHeight - rightHeight) > 1) return false;
    return isBalanced(root.left) && isBalanced(root.right);
}

private int height(TreeNode root) {
    if (root == null) return 0;
    int leftHeight = height(root.left);
    int rightHeight = height(root.right);
    return Math.max(leftHeight, rightHeight) + 1;
}

算法流程:

1. 二叉树为空的情况是平衡的,直接返回 true。
2. 计算当前根节点的左子树高度 leftHeight 和右子树高度 rightHeight。
3. 如果两子树高度差的绝对值大于 1,直接返回 false。
4. 递归判断左子树和右子树是否平衡。
5. 如果左右子树都是平衡的,则整棵树是平衡的,返回 true。

时间复杂度 O(nlogn),空间复杂度 O(n)。

所以,判断平衡二叉树的关键是:

1. 计算左右子树的高度,如果差值大于 1 则不是平衡二叉树,返回 false。
2. 递归判断左右子树是否平衡。
3. 只有左右子树均平衡,整棵树才平衡,返回 true。