题目描述：
输入一棵二叉树，判断该二叉树是否是平衡二叉树。
如果某二叉树中任意结点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。例如，下图中的二叉树就是一棵平衡二叉树。
解题思路：
解题思路有两种，只遍历一次的方法最优。
重复遍历多次：
在遍历树的每个结点的时候，调用函数treedepth得到它的左右子树的深度。如果每个结点的左右子树的深度相差都不超过1，则这是一颗平衡的二叉树。这种方法的缺点是，首先判断根结点是不是平衡的，需要使用treedepth获得左右子树的深度，然后还需要继续判断子树是不是平衡的，还是需要使用treedepth获得子树的左右子树的深度，这样就导致了大量的重复遍历。
只遍历一次：
重复遍历会影响算法的性能，所以很有必要掌握不需要重复遍历的方法。如果我们用后序遍历的方式遍历二叉树的每一个结点，在遍历到一个结点之前我们就已经遍历了它的左右子树。只要在遍历每个结点的时候记录它的深度（某一结点的深度等于它到叶结点的路径的长度），我们就可以一边遍历一边判断每个结点是不是平衡的。
代码实现(c )
重复遍历多次实现：
class solution {
public:
bool isbalanced_solution(treenode* proot) {
if(proot == null){
return true;
}
int left = treedepth(proot->left);
int right = treedepth(proot->right);
int diff = left - right;
if(diff > 1 || diff < -1){
return false;
}
return isbalanced_solution(proot->right) && isbalanced_solution(proot->left);
}
private:
int treedepth(treenode* proot)
{
if(proot == null){
return 0;
}
int left = treedepth(proot->left);
int right = treedepth(proot->right);
return (left > right) ? (left 1) : (right 1);
}
};
只遍历一次实现：
class solution {
public:
bool isbalanced_solution(treenode* proot) {
int depth = 0;
return isbalanced(proot, &depth);
}
private:
int isbalanced(treenode* proot, int* depth){
if(proot == null){
*depth = 0;
return true;
}
int left, right;
if(isbalanced(proot->left, &left) && isbalanced(proot->right, &right)){
int diff = left - right;
if(diff <= 1 && diff >= -1){
*depth = 1 (left > right ? left : right);
return true;
}
}
return false;
}
};