Balanced Binary Tree Problem

Problem description:
level: medium

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}

The binary tree A is a height-balanced binary tree, but B is not.

Solution:

consider a node, if left is balanced, right is balanced, and left, right nodes height difference < 2, then the node is balanced

Another thought:
if a node is not balanced, then its height set to -1
else return it is real height

Using Divide & Conquer, we can get the height to decide if it is a balanced tree


    /**
     * @param root: The root of binary tree.
     * @return: True if this Binary tree is Balanced, or false.
     */
    public boolean isBalanced(TreeNode root) {
    	if(root == null) return true;
    	
    	boolean left = isBalanced(root.left);
    	boolean right = isBalanced(root.right);
    	int leftHeight = maxHeight(root.left);
    	int rightHeight = maxHeight(root.right);
    	
    	return left && right && Math.abs(leftHeight - rightHeight) < 2;
    	
    }
	

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