【剑指offer】面试题39扩展：平衡二叉树

题目：

输入一棵二叉树，判断该二叉树是否是平衡二叉树。

思路：

直观的思路是，判断根结点的左子树、右子树高度差是否小于1。

为避免多次访问同一结点，应该用后序遍历的方式访问。

注意：加号优先级高于条件运算符

Code：

class Solution {
public:
    bool IsBalanced_Solution(TreeNode* pRoot) {
        if(isBalanced(pRoot)<0)  return false;
        else return true;
    }
private:
    int isBalanced(TreeNode* pRoot)
    {
        if(pRoot==NULL)  return 0;
        
        int left=0,right=0;
        if(pRoot->left!=NULL)
            left=isBalanced(pRoot->left);
        if(left<0)  return left;
        
        if(pRoot->right!=NULL)
            right=isBalanced(pRoot->right);
        if(right<0)  return right;
        
        if(left-right<-1 || left-right>1)  return -1;//不平衡
        
        return (left>right?left:right)+1;//平衡，则返回树的高度  注意：加号的优先级高于条件运算符！！！
    }
};

书上形式的代码

class Solution {
public:
    bool IsBalanced_Solution(TreeNode* pRoot) {
        int depth=0;
        return IsBalanced(pRoot,&depth);
    }
private:
    bool IsBalanced(TreeNode* pRoot, int* depth)
    {
        if(pRoot==NULL)
        {
            *depth=0;
            return true;
        }
        
        int left=0,right=0;
        if(IsBalanced(pRoot->left,&left) && IsBalanced(pRoot->right,&right))
        {
            if(left-right<=1 && left-right>=-1)
            {
                *depth=(left>right?left:right)+1;
                return true;
            }
        }
        return false;
    }
};