题目
输入一棵二叉树，判断该二叉树是否是平衡二叉树。
分析
所谓的平衡二叉树（又叫平衡二叉查找树）指的是：
（1）空树
（2）不是空树，任何一个节点的左右子树均是平衡二叉树，并且高度之差不超过1
先了解几个概念：
（1）平衡因子：节点左右子树的深度之差；
（2）最小不平衡树；距离插入点最近，并且平衡因子的绝对值大于1的节点为根节点的子树。
平衡二叉树的构造：
每当插入一个节点的时候，首先检查二叉树是否因为插入而失去了平衡，也就是插入节点之后，是不是存在节点的左右子树的深度差>1，若是，找出最小不平衡树，然后进行 相应的旋转，使之能够满足平衡二叉树的要求。
具体到本题：
我们可以从根节点开始，判断每一个节点的左右子树的深度之差是否超过了1，当前节点判断完之后，再分别判断当前节点的左右子节点，这样的思想会重复计算很多次：
public class Solution {
public boolean IsBalanced_Solution(TreeNode root) {
if(root == null)
return true;
int leftDepth = getDepth(root.left);
int rightDepth = getDepth(root.right);
if(Math.abs(leftDepth - rightDepth) > 1){
return false;
}
return IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right);
}
public int getDepth(TreeNode root){
if(root == null)
return 0;
int left = getDepth(root.left)+1;
int right = getDepth(root.right)+1;
return left>right?left:right;
}
}
假如我们进行后续遍历，因为后续遍历时，所有的节点都被读了一遍，所以我们可以一边遍历，一边比较：
public class Solution {
//后续遍历时，遍历到一个节点，其左右子树已经遍历 依次自底向上判断，每个节点只需要遍历一次
// 标志位
private boolean isBalanced_tree = true;
public boolean IsBalanced_Solution(TreeNode root) {
if(root == null)
return isBalanced_tree;
getDepth(root);
return isBalanced_tree;
}
public int getDepth(TreeNode root){
if(root == null)
return 0;
// 左子树的深度
int leftDepth = getDepth(root.left);
// 右子树的深度
int rightDepth = getDepth(root.right);
// 如果左右子树的高度差超过1，返回返回错误
if((leftDepth - rightDepth)<-1 || (leftDepth - rightDepth)>1)
isBalanced_tree = false;
return leftDepth > rightDepth ? leftDepth+1 : rightDepth+1;
}
}
