一.题目大意
输入一颗二叉树，判断该二叉树是否为平衡二叉树(AVL树)。
二.题解
《剑指offer》上给出了两种解决方式：
1.第一种是从根节点开始，从上往下遍历每个子节点并计算以子节点为根节点的子树的高度，通过判断左右子树的高度差是否大于1来判断是否为AVL树。其中计算子树的高度，利用了TreeDepth函数(具体可见《剑指offer(第二版)》P272).其中TreeDepth的思想如下：
(1)计算一颗二叉树的高度，可以将该问题转化成求子树的高度+1。如果根节点只有左子树的话，那么该二叉树的高度=左子树的高度+1.
(2)如果根节点只有右子树的话，那么该二叉树的高度=右子树的高度+1.
(3)如果根节点既有左子树又有右子树的话，那么该二叉树的高度等于左子树和右子树中高度的较大值加1.
这很显然利用分治的思想就可以解决。
利用TreeDepth函数判断是否为AVL树的话，很多节点往往会重复遍历多次，所以效率会比较低。
2.第二种《剑指offer》上给出的思想是：利用后序遍历的思想，每次遍历到某个节点时，它的左右子树一定已经遍历完了，所以只需在遍历每个节点的时候记录该节点的深度(某一节点的深度等于该节点到叶节点的长度)，就可以一边遍历一边判断每个节点是否平衡。
代码可参考书上P274的带代码，但我觉得这种方法不够形象，所以便有了第3种方法。
3.这种方法是这篇文章强调的重点。我们可以利用TreeDepth函数的思想，同样也是分治的思想：
要判断一棵二叉树是否为AVL树，只需判断它的左子树和右子树是否都为AVL数，如果都是AVL树的话，那么这棵树一定是AVL数；对于左子树和右子树的判断进行同样的操作。这就将父问题转换成了一系列的子问题，一旦子问题中有一个不满足的，就返回结果。
代码如下：
class Solution {
public:
bool IsBalanced_Solution(TreeNode* pRoot) {
if(pRoot == nullptr)//此处需要注意，空树的话也是AVL树
return true;
return GetAVLDepth(pRoot) != -1;//返回-1相当于不是AVL树
}
int GetAVLDepth(TreeNode* pRoot)
{
if(pRoot == nullptr)//空的情况返回0
return 0;
int left = GetAVLDepth(pRoot->left);
if(left == -1)//如果子树不是AVL树的话，立马返回，此处相当于剪枝，这步是必须要加的，否则可能出错
return -1;
int right = GetAVLDepth(pRoot->right);
if(right == -1)
return -1;
return abs(left - right) > 1 ? -1 : (max(right,left) + 1);//只有左右子树都为AVL树的话才会返回这棵树的高度
}
};
这种方法是的思想本质与求二叉树的高度的思想是一致的，只不过在返回时，只有左右子树都为AVL树的话才会返回数的高度，否则返回-1(即非AVL树)，所以值得回味与思索。还有一点需要注意的是，当根节点为空时，此时是棵空树，但它也是AVL树。最为重要的一点是，如果遇到左子树或者右子树不是AVL树的话，应立马返回-1，否则，后续处理可能出错。
方法3相比方法2在代码上更容易理解，更加形象些。