Balanced Binary Tree

题目：

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

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

分析：

这道题目上的logic要再注意一下，我用了个getHeight，做了两个嵌套的recursion，虽然结果是对的但是复杂度肯定不好

这题目九章用result type的方法做了，但是其实更简单的是用-1表示unbalance的情况，直接用个getHeight就能做出来

解法：

public class Solution {
    /**
     * @param root: The root of binary tree.
     * @return: True if this Binary tree is Balanced, or false.
     */
    public int getHeight(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int lHeight = getHeight(root.left);
        int rHeight = getHeight(root.right);

        if (lHeight == -1 || rHeight == -1 || Math.abs(lHeight - rHeight) > 1) {
            return -1;
        }

        return Math.max(lHeight, rHeight) + 1;
    } 

    public boolean isBalanced(TreeNode root) {
        // write your code here
        if (root == null) {
            return true;
        }
        if (root.left == null && root.right == null) {
            return true;
        }
        return getHeight(root) != -1;
    }
}