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.

Example

Given binary tree A = {3,9,20,#,#,15,7}, B = {3,#,20,15,7}

A)  3            B)    3 
   / \                  \
  9  20                 20
    /  \                / \
   15   7              15  7

经典的divide and conquer

先看左右子树是不是balanced，然后再看高度差是否为1

public class Solution {
    /**
     * @param root: The root of binary tree.
     * @return: True if this Binary tree is Balanced, or false.
     */
    //height
    //isBalanced
    private class ResultType{
        int height;
        boolean isBalanced;
        private ResultType(int height, boolean isBalanced){
            this.height = height;
            this.isBalanced = isBalanced;
        }
    }
    public boolean isBalanced(TreeNode root) {
        // write your code here
        if (root == null) {
            return true;
        }
        ResultType res = helper(root);
        return res.isBalanced;
    }
    public ResultType helper( TreeNode root) {
        if (root == null) {
            return new ResultType(0, true);
        }
        ResultType left = helper(root.left);
        ResultType right = helper(root.right);
        if (!left.isBalanced || !right.isBalanced) {
            return new ResultType(0, false);
        }
        if (Math.abs(left.height - right.height) > 1) {
            return new ResultType(0, false);
        }
        return new ResultType(Math.max(left.height, right.height) + 1, true);

    }
}