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.

这道题比较直观的解法对于每个点的左右子树都用Maximum Depth of Binary Tree的方法求解并进行合法检查。但这样会有很多重复的操作。
递归的求解左右子树的深度，看是否符合平衡要求。

public class Solution {
    //Time: O(n)  Space: O() depends on the structure of tree
    public boolean isBalanced(TreeNode root) {
        return checkBalance(root) != -1;
    }
    
    private int checkBalance(TreeNode root) {
        if (root == null) {
            return 0;
        }
        
        int left = checkBalance(root.left);
        int right = checkBalance(root.right);
        if (left == - 1 || right == -1) {
            return -1;
        }
        
        return Math.abs(left - right) <= 1 ? 1 + Math.max(left,right) : -1;
    }
}