题目
题目：输入一棵二叉树，判断该二叉树是否是平衡二叉树。
注：这个题思路很好，可以经常看。
解法一
思路
一般来说，平衡二叉树既是平衡的树，又是二分搜索树。但此题只要求判断是不是平衡的。
判断一棵树是否是平衡的，就是判断所有的节点是不是平衡的。
判断一个节点是不是平衡的，就是判断左右子节点的高度差是否<=1。
如果学过AVL树，思路是一样的，但是却有一点不同，AVL树的TreeNode结构体(每个节点)中有一个成员表示高度，在每次插入节点的时候就会更新每个节点的高度，所以判断是否平衡的时候可以直接判断是否为平衡的。
而这个题的TreeNode结构体如下所示：
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};
这个结构体并没有保存高度信息，所以第一个想法是写一个求高度的函数，分别对左右子树求高度，再看高度差受否满足平衡二叉树的要求。
求树的高度可以使用递归法，树的高度等于左右子树高度的最大值再加上1（自身节点高度为1），递归代码如下：
int getHeight(TreeNode *node){
if(node == NULL)
return 0;
return 1 + max(getHeight(node->left), getHeight(node->right));
}
判断当前节点是否平衡，就是计算左右子树的高度差。
判断当前树是不是平衡，就是判断当前节点、当前节点的左子树、当前节点的右子树是否平衡，还是个递归问题。
代码
class Solution {
public:
// 递归求高度
int getHeight(TreeNode *node){
if(node == NULL)
return 0;
return 1 + max(getHeight(node->left), getHeight(node->right));
}
//判断该节点是否平衡
bool IsBalanced(TreeNode *node){
if(node == NULL)
return true;
if(abs(getHeight(node->left) - getHeight(node->right)) > 1)
return false;
return true;
}
bool IsBalanced_Solution(TreeNode* pRoot) {
if(pRoot == NULL)
return true;
return IsBalanced(pRoot) && IsBalanced(pRoot->left) && IsBalanced(pRoot->right);
}
};
代码提交后，成功过关。
解法二
思路
虽然成功的做出了这个题，但是总觉得有很别扭的地方。
为了求判断某个节点是不是平衡，需要求左右子树的高度，判断完该节点之后，又需要判断左子树是不是平衡，这个时候又需要计算左子树的左右子树的高度，讲道理，第一次递归求根节点的高度时，下面的节点的高度已经被计算过了，但是却没有被记录下来，导致白白遍历了很多次。
借鉴动态规划中的记忆化搜索，可以使用map<TreeNode*, int> mp来记录每个节点的高度，如果发现计算过，就直接返回记录的值。
这样应该能解决重复递归的问题，但是又增加了空间复杂度。
看了下别人的思路，豁然开朗。原先的做法中，在求当前节点的高度时，递归计算下面了所有节点的高度，但是却没有充分利用这些高度值。其实这个时候可以多做一件事情，判断该节点是不是平衡的！如果不平衡，可以提前结束递归。
代码
class Solution {
public:
int getHeight(TreeNode *node){
if(node == NULL)
return 0;
int left = getHeight(node->left); //求左子树的高度
if(left == -1) return -1; //求左子树的高度的时候发现了该节点不平衡
int right = getHeight(node->right);
if(right == -1) return -1;
return abs(left - right) > 1 ? -1 : 1 + max(left, right); //求该节点的高度
}
bool IsBalanced_Solution(TreeNode* pRoot) {
return getHeight(pRoot) != -1;
}
};
思路还是有点绕，举个栗子：
如上图，递归的步骤是：
- 求节点
1的高度时，递归到了叶子节点4，左右节点的高度值都为0，可以判断出节点4是平衡的，所以求的节点4的高度值为1，并将这个高度值返回递归的上一层！！！ - 这时返回上一层，到了节点
3。它得到到了左节点4的高度值1，继续递归计算右节点的高度，得到高度值0，所以节点3满足平衡条件，且自身的高度值为2，又将这个高度值返回给上一层。 - 又返回了上一层，到了节点
2。它得到到了左节点3的高度值2，继续递归计算右节点的高度，得到高度值0，这个时候就发现节点2是不平衡的了！没有必要继续再计算高度了，直接层层返回失败就行了。由于返回值是int，所以设定返回-1就是失败。这也就是为什么需要在得到高度后判断是不是-1的原因。 - 最后只需要保证根节点的高度值不是-1就说明是这棵树是平衡的了
总结
递归是个大杀器，也难以利用，不要重复递归。
递归说到底还是个栈，只是利用了函数调用形成的栈。
