判断是否为平衡二叉树

题目描述：

给定一棵二叉树，判断是否为平衡二叉树

解题思路：

• 在解决这道题时，我们首先要知道什么是平衡二叉树
• 平衡二叉树的性质：左右子树高度差小于等于1
• 只有根节点的树是平衡二叉树，空树也是平衡二叉树
  代码实现：
  

每个节点只遍历一次的方法
如果我们用后序遍历的方式遍历二叉树的每个结点，在遍历一个结点之前我们就已经遍历了它的左右子树。只要在遍历每个结点的时候我们记录它的深度（某一节点的深度等于它到叶结点的路径的长度），我们就可以一边遍历一边判断每个结点是不是平衡二叉树。

class Solution {
public:
    bool IsBalanced_Solution(TreeNode* pRoot) {
        int depth=0;
        return IsBalance(pRoot,depth);
    }
    //
    bool IsBalance(TreeNode* pRoot,int &height)
    {
        if (pRoot == NULL)
        {
            height = 0;
            return true;
        }

        int leftHeight = 0, rightHeight = 0;
        bool leftRet = IsBalance(pRoot->left, leftHeight);//判断左子树
        bool rightRet = IsBalance(pRoot->right, rightHeight);//判断右子树

        height = max(leftHeight, rightHeight) + 1;//当前结点树的高度
        if (abs(leftHeight - rightHeight) > 1)
            return false;
        return leftRet && rightRet;//递归遍历
    }
 };