image
题目
给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1
解题思路
根据题目中高度平衡的定义，这道题就转换了求左右子树高度的绝对值，小于等于1就是平衡二叉树。这个就是这道题的子问题，我们只要迭代这个子问题就可以了，如果一棵树上的所有节点都满足这个条件，那么这个树就是一个平衡二叉树。求二叉树的深度，我们之前有过类似的题目LeetCode二叉树专题 (4) 二叉树的最大深度
现在我们想这么一个问题，如果从跟节点判断起，再判断他的左右节点，这样是不是会重复计算很多次底部树的深度，显然这样的效率是很低，所以我们最好是从底部开始算起，这样底部的数据就可以让顶层的节点使用，不需要重复计算了。
public boolean isBalanced(TreeNode root) {
//-1标记不符合平衡的条件
return getDeep(root) != -1;
}
public int getDeep(TreeNode root){
if(root == null){
return 0;
}
int left = getDeep(root.left) + 1;
int right = getDeep(root.right) + 1;
if(left == 0 || right == 0){
//如果有一个节点不满足，那么所有都直接返回-1
return -1;
}
if(Math.abs(left-right) > 1){
//这个节点的左右最大深度差值大于1，不是平衡的
return -1;
}
//返回左右的深度
return Math.max(left,right);
}
