p110

 

 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class  {
    public boolean isBalanced(TreeNode root) {
        if (root == null || (root.left == null && root.right == null))
			return true;
		if (dp(root) < 0)
			return false;
		else {
			return true;
		}

	}

	public int dp(TreeNode root) {

		if (root == null)
			return 0;
		int a = dp(root.left);
		int b = dp(root.right);
		if (a == -1 || b == -1) {
			return -1;
		}
		int l = a > b ? a - b : b - a;
		if (l > 1)
			return -1;
		else {
			return Math.max(a, b) + 1;
		}

	}
}