题目

判断一棵二叉树是否是平衡二叉树。（平衡二叉树每个节点的左右两个子树的高度差的绝对值不超过1。）

解题方法

1. 从根节点开始，首先判断其左右子树高度差的绝对值是否小于等于1，否则直接判定不是平衡二叉树；
2. 当step1中左右子树高度差的绝对值小于等于1时，分别判断左右孩子节点是否满足平衡条件；
3. 同样左右孩子判断他们的左右子树高度差，然后再继续判断他们的左右孩子节点，依次递归。

注意：这里不同于之前的递归实现，之前的递归大多只需要获取依赖的上一步递归结果即可，这里除了上一步的左右子树是否平衡的递归结果以外，还需要判断自身的左右子树高度差。

代码

public boolean isBalanced(TreeNode root) {
    if(root == null){//空树为平衡树
        return true;
    }
    int lh = treeHeight(root.left);//左子树高
    int rh = treeHeight(root.right);//右子树高
    if(Math.abs(lh - rh) > 1){//如果左右子树高度差绝对值超过1，则不平衡
        return false;
    }
    //递归判断节点的左右孩子节点是否满足平衡条件
    return isBalanced(root.left) && isBalanced(root.right);
}

//二叉树树高
private int treeHeight(TreeNode root){
    if(null == root){//空节点高为0
        return 0;
    }
    int leftHeight = treeHeight(root.left);//左子树树高
    int rightHeight = treeHeight(root.right);//右子树树高
    //当前节点高为左右子树高度最大值加1
    return leftHeight >= rightHeight ? (leftHeight + 1) : (rightHeight + 1);
}