Given a binary tree, determine if it is height-balanced.

方法1

1. 如果已经不平衡，则递归一直返回-1即可，也没有继续比较的必要了。
2. 否则就利用返回的深度信息看看左右子树是不是违反平衡条件，如果违反返回-1，
3. 否则返回左右子树深度大的加一作为自己的深度即可。

    public boolean isBalanced(TreeNode root) {
        return helper(root) >= 0;
    }

    private int helper(TreeNode root) {
        if (root == null) return 0;
        //这样会把所有node都当做root遍历一遍。TimeComplexity:O(n)
        int lh = helper(root.left);
        int rh = helper(root.right);
        //这句不能落下。。。
        if (lh == -1 || rh == -1) {
            return -1;
        }
        if (Math.abs(lh - rh) >= 2) {
            //技巧：返回-1代表某棵subtree imbalance 了
            return -1;
        }
        return Math.max(helper(root.left), helper(root.right)) + 1;
    }

方法2

Calling height() explicitly for each child node

    public boolean isBalanced(TreeNode root) {
        if (root == null) return true;
        int lh = height(root.left);
        int rh = height(root.right);
        return Math.abs(lh - rh) <= 1 && isBalanced(root.left) && isBalanced(root.right);

    }

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