[LeetCode]Balanced Binary Tree

Bottom-up的做法，先得到左子树和右子树的高度。如果发现左子树或者右子树已经不是balanced的话(return的值是-1)，return -1，然后看以当前node为root的subtree是不是balanced的，即计算左右子树的高度差是不是小于等于1，不是的话return -1，否则，计算当前node的高度，return高度。代码如下：

	/**
	* Definition for binary tree
	* public class TreeNode {
	* int val;
	* TreeNode left;
	* TreeNode right;
	* TreeNode(int x) { val = x; }
	* }
	*/
	public class Solution {
	public boolean isBalanced(TreeNode root) {
	int res = getBalance(root);
	return res == -1? false: true;
	}
	private int getBalance(TreeNode node) {
	if (node == null)
	return 0;
	int left = getBalance(node.left);
	int right = getBalance(node.right);
	if (left == -1 || right == -1)
	return -1;
	int diff = abs(left - right);
	return diff > 1? -1: max(left, right) + 1;
	}
	private int abs(int x) {
	return x < 0? -x: x;
	}
	private int max(int a, int b) {
	return a >= b? a: b;
	}
	}

view raw balanced binary tree.java hosted with ❤ by GitHub