Balanced Binary Tree

判定平衡二叉树的题目是一道基本的数据结构题目，在Leetcode的OJ上也有相关的测试用例。二叉树的结构请参见《Leetcode中使用的二叉树结构》。

可以使用一个递归函数，递归的判断每个节点的左子树和右子树的高度是否相差1，但是这样的算法会产生很多次重复的计算，效率并不高。另外一种方法是设计一个递归函数，返回以每个节点为根的二叉树的高度，当左右子树返回的高度相差超过1时，则返回-1表示该树不平衡。这样的算法时间复杂度为O(n)。该算法的Java实现如下。

public class Solution {

	/**
	 * 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.
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		TreeNode root = new TreeNode(1);
		root.left = new TreeNode(2);
		root.right = new TreeNode(3);
		root.left.left = new TreeNode(4);
		root.left.right = new TreeNode(5);
		root.right.left = new TreeNode(6);
		root.right.right = new TreeNode(7);

		
		System.out.print(new Solution().isBalanced(root));
	}
	
	public boolean isBalanced(TreeNode root) {
        // Start typing your Java solution below
        // DO NOT write main() function
		
		if(height(root) == -1)
			return false;
		else
			return true;
    }
	
	public int height(TreeNode n){
		int left_b, right_b;
		
		if(n == null){
			return 0;
		}
		else{
			left_b = height(n.left);
			right_b = height(n.right);

			if (left_b == -1 || right_b == -1) {
				return -1;
			} else if (Math.abs(left_b - right_b) <= 1) {
				return Math.max(left_b, right_b)+1;
			} else {
				return -1;
			}
		}
	}

}