平衡二叉树

时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
题目描述
输入一棵二叉树，判断该二叉树是否是平衡二叉树。

---

知识介绍：

• 平衡二叉树，是一种二叉排序树，它的每个结点的左子树和右子树的高度差不超过1。是一种高度平衡的二叉排序树。

思路：

• 采用深度优先搜索的方式获取根节点的左子树、右子树的高度并计算高度差，若高度差大于1则直接返回，若小于等于1，则以左子树的根节点作为新的二叉树，递归遍历该子树的左右子树的高度及高度差，右子树同理。

class Solution {
public:
    bool IsBalanced_Solution(TreeNode* pRoot) {
        if(!pRoot)
            return true;
        //得到的是整棵树的高度
        int ldepth = TreeDepth(pRoot->left);
        int rdepth = TreeDepth(pRoot->right);
        if(abs(ldepth-rdepth) > 1)
            return false;
        //递归左子树、右子树的高度
        return IsBalanced_Solution(pRoot->left) && IsBalanced_Solution(pRoot->right);
    }
    int TreeDepth(TreeNode* root)
    {
        if(!root)
            return 0;
        int ldepth = TreeDepth(root->left);
        int rdepth = TreeDepth(root->right);
        return 1+(ldepth>rdepth?ldepth:rdepth);
    }
};

• 采用后序遍历，从叶子结点开始，判断左子树与右子树的高度差是否符合平衡二叉树的条件

class Solution {
public:
    bool IsBalanced_Solution(TreeNode* pRoot) {
        int depth = 0;
        return IsBalanced_Solution(pRoot,depth);
    }
    bool IsBalanced_Solution(TreeNode* pRoot,int &depth)
    {
        if(!pRoot)
        {
            depth = 0;
            return true;
        }
             
        int ldepth,rdepth;
        if(IsBalanced_Solution(pRoot->left,ldepth)&&IsBalanced_Solution(pRoot->right,rdepth))
        {
            if(abs(ldepth - rdepth) <=1)
            {
                depth = 1 + max(ldepth,rdepth);
                return true;
            }
        }
        return false;
    }
};