给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1。
示例 1:
给定二叉树 [3,9,20, null, null, 15,7]
3
/ \
9 20
/ \
15 7
返回 true 。 示例 2:
给定二叉树 [1,2,2,3,3, null, null, 4,4]
1
/ \
2 2
/ \
3 3
/ \
4 4
对于这个问题，我们可以非常快的写出递归版本。当root为空的时候，我们将None也看成是一棵二叉树，所以返回True。接着我们判断左子树高度和右子树高度差是不是大于1，如果是，那么我们返回False就好啦。如果不是接着递归判断左子树和右子树是不是一棵平衡二叉树。
public boolean isBalanced(TreeNode root) {
//自下而上
//如果节点为空
if(root==null) return true;
//如果左右子树高度差大于1
int left = getDepth(root.left);
int right = getDepth(root.right);
if(Math.abs(left-right)>1) return false;
//递归左右子树
return isBalanced(root.left) && isBalanced(root.right);
}
private int getDepth(TreeNode root) {
//如果节点为空
if(root==null) return 0;
//递归左右子树
return Math.max(getDepth(root.left),getDepth(root.right))+1;
}但是如你所见，这个解法有一个很明显的弊端，就是我们在每次求height的时候有大量的重复运算，我们怎么可以避免这种重复运算呢？或者说我们有什么办法在遍历一遍树（求一次height）的过程中就可以得到答案呢？我们希望当左右子树中存在不平衡的时候就可以提前停止。
public boolean IsBalanced_Solution (TreeNode pRoot) {
// write code here
return getDepth(pRoot) != -1;
}
public int getDepth(TreeNode root) {
//从下往上遍历，如果子树是平衡二叉树，则返回子树的高度；如果发现子树不是平衡二叉树，则直接停止遍历
if (root == null) return 0;
int left = getDepth(root.left);
if (left == -1) return -1;
int right = getDepth(root.right);
if (right == -1) return -1;
return Math.abs(left - right) > 1 ? -1 : 1 + Math.max(left, right);
}上面这种解法非常的巧妙，当树出现不平衡的时候，我们令树的高度是-1。