Balanced Binary Tree
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.
解法1：
1.计算每个节点的高度
2.从根节点开始从上往下遍历，判断每个节点的左右子树是否是平衡的
缺点：每次遍历都要重新计算高度，很多节点的高度都重复计算了，时间复杂度o（n^2）
解法2：
从根节点开始，从上往下遍历，按照中序遍历的思想，从左右子节点向根节点遍历，一依次判断平衡状态，这样根结点可以重复利用已经计算的子节点的高度，只需要依次遍历整棵树。在遇到某个子树非平衡时，能直接结束，返回false。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
import java.math.*;
public class Solution {
public boolean isBalanced(TreeNode root) {
if(root == null)
return true;
int leftH = getHeight(root.left);
int rightH = getHeight(root.right);
int diff = leftH - rightH;
if(diff>1 || diff<-1){
return false;
}else{
return isBalanced(root.left) && isBalanced(root.right);
} } int getHeight(TreeNode root){
if(root == null){
return 0;
}
return 1+Math.max(getHeight(root.left),getHeight(root.right));
} /**
public boolean isBalanced(TreeNode root) {
if(root == null)
return true; if(getHeight(root) == -1){
return false;
}else{
return true;
}
} public int getHeight(TreeNode root){
if(root == null)
return 0; int leftH = getHeight(root.left);
if(leftH == -1)
return -1; int rightH = getHeight(root.right);
if(rightH == -1)
return -1; if(leftH-rightH > 1 || leftH-rightH < -1)
return -1; return 1+(leftH>rightH?leftH:rightH); }
*/
}