Balanced Binary Tree @LeetCode

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.

	package leetcode.tree;
	/**
	* Thought: Check left and right tree, campare their maxPath, if > 1, not balanced.
	*
	* left == -1 means the child is already not balanced
	* right == -1
	*
	* if (Math.abs(left - right)) > 1 must contains condition left == -1 and right == -1
	* Or, return -1 compare with 0, return 0, test case as follows.
	* 1
	* 1 1
	* 1 1
	* 1 1
	*
	* @author jeffwan
	* @date Feb 11, 2014
	*/
	public class IsBalanced {
	public boolean isBalanced (TreeNode root) {
	return maxDepth(root) != -1;
	}
	private int maxDepth(TreeNode root) {
	if (root == null) {
	return 0;
	}
	int left = maxDepth(root.left);
	int right = maxDepth(root.right);
	if (left == -1 || right == -1 || Math.abs(left - right) > 1) {
	return -1;
	}
	return Math.max(left, right) + 1;
	}
	// TreeNode
	private class TreeNode {
	int val;
	TreeNode left;
	TreeNode right;
	TreeNode (int x) {
	val = x;
	}
	}
	}

view raw IsBalanced.java hosted with ❤ by GitHub