IsBalancedOneRecursive
这种最容易写的方法就是严格按定义，BBT(Balanced Binary Tree)：要么空，要么左右子树高度相差最多1，且左右子树都为BBT。显然递归定义，判定也是递归的，
因此根据这句描述，有句求高度的语句，我之前用了朴素的调用计算高度的函数，而且这个是递归写的，当然用站站的层序遍历也是可以的，当时两层递归居然也让我过了，对我有点放任了= =
class Solution {
public:
int Depth(TreeNode* root)
{
if(root==NULL) return 0;
int leftdepth=Depth(root->left);
int rightdepth=Depth(root->right);
if(leftdepth>rightdepth) return 1+leftdepth;
else return 1+rightdepth;
}
bool isBalanced(TreeNode *root) {
if(root==NULL) return true;
int leftDepth=Depth(root->left);
int rightDepth=Depth(root->right);
return abs(leftDepth-rightDepth)<=1 && isBalanced(root->left) && isBalanced(root->right);
}
};
后来想想有么有一次递归搞定的，也即递归判定二叉树的同时 ，还可以计算出高度来？
自己想的时候还不是很清晰，后来看了一篇似乎很强的童鞋写的一堆递归解二叉树问题的代码，瞬间觉得有了思路。
为什么自己没这么想，主要是不知道怎么把height这个副产品潜逃到递归函数里面。后来看了下，觉得自己还是要严格按照定义来。
IsBBT(root)+height: root==NULL || (|leftheight-rightheight|<=1 && IsBBT(root->left) && IsBBT(root->right) )
这句逻辑语句把代码高度概括了，但是leftheight不用调用外部函数的方法来实现，那怎么弄呢？
仔细看height定义： root_height=max(root->left_height,root->right+height)+1,
IsBBT肯定还是返回bool，结果，里面如果要把副产品height算出来，只能引用传递，因为要把root的height返回回来，所以子树调用的时候，用leftheight=0 引用传递进去，调用完成后，就是树高了，
然后切记，每个递归出口同样要加上计算height这个副产品的语句，root空 height=0，如果有子树，并且满足定义，height=max(leftheight,rightheight)+1 然后返回主要的bool值，因此代码如下：
class Solution {
public:
bool isBalanced(TreeNode *root) {
int height=0;
return isBalancedHeight(root,height);
}
bool isBalancedHeight(TreeNode* root,int& height)
{
if(root==NULL) {height=0;return true;}
else
{
int leftheight=0;
bool leftisBalanced=isBalancedHeight(root->left, leftheight);
int rightheight=0;
bool rightisBalanced=isBalancedHeight(root->right, rightheight);
if(leftisBalanced && rightisBalanced && abs(leftheight-rightheight)<=1)
{
height=max(leftheight,rightheight)+1;
return true;
}
else
{
height=max(leftheight,rightheight)+1;
return false;
}
}
}
};
当然和前面一样，直接用函数返回值作为临时变量也是可以的，因为函数返回值只用来逻辑判断一次就可以了，不需要保留，引用传递的值调用完也就算完了。
代码改成如下的：
class Solution {
public:
bool isBalanced(TreeNode *root) {
int height=0;
return isBalancedHeight(root,height);
}
bool isBalancedHeight(TreeNode* root,int& height)
{
if(root==NULL) {height=0;return true;}
else
{
int leftheight=0;
int rightheight=0;
if(isBalancedHeight(root->left, leftheight) && isBalancedHeight(root->right, rightheight) && abs(leftheight-rightheight)<=1)
{
height=max(leftheight,rightheight)+1;
return true;
}
else
{
height=max(leftheight,rightheight)+1;
return false;
}
}
}
};
因为鄙人之前都直接函数作为临时变量来参与逻辑判断语句，逻辑更精炼，这里三个与编译器会先算前两个，算完之后leftheight rightheight也都算出来了，所以后面应该不会出错
顺便赋上似乎很牛的博客：http://blog.csdn.net/luckyxiaoqiang/article/details/7518888