Leetcode : Balanced Binary Tree
Leetcode中文站：平衡二叉树
Diffculty：Easy
关键字：Tree，递归
描述：
判断一棵树是否是高度平衡的二叉树。
在本题中，高度平衡二叉树定义为：一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1
思路：
其实思路很简单，使用递归可以很容易写出。
1、判断左子树是否平衡
2、判断右子树书否平衡
3、判断左右子树高度差是否小于等于1.（当前节点为root是否平衡）
要注意的点：
在Leetcode中文站官方解中，给出了两种方式，自顶向下和自底向上。但这两种方式都不可避免的进行了多余的递归和多余的计算。
1、判断平衡 和 计算高度。这两个操作都会对树进行递归。如果分开操作，那么会有两次递归。
2、如果有某一个子树不平衡，那么整个树就不平衡，可以直接返回结果。而不需要再去计算其他子树了。
我的思路：
就是解决上面两点的问题。
1、在判断子树平衡的同时，计算树的高度。如果平衡则返回高度，不平衡返回-1。
2、如果子树不平衡直接快速失败，避免重复计算。
运行结果：
时间：1ms, beats 99.97%
空间：38.4MB, beats 82.19%
public boolean isBalanced(TreeNode root) {
if(root == null) return true;
return balanceDepth(root, 1) > 0;
}
/**
* 思路：
* 1、一次递归。在判断子树平衡的同时返回高度。如果不平衡则返回-1
* 2、快速失败。当判断到某一个子树不平衡时直接返回失败，不再往下递归。
* @param node
* @param depth
* @return
*/
private int balanceDepth(TreeNode node, int depth){
if(node == null){
return depth;
}
int leftDepth = balanceDepth(node.left, depth);
if(leftDepth < 0) {
return -1;
}
int rightDepth = balanceDepth(node.right, depth);
if(rightDepth < 0){
return -1;
}
if(Math.abs(leftDepth-rightDepth) <=1){
return depth + Math.max(leftDepth, rightDepth);
}
return -1;
}
