平衡二叉树

题目描述

输入一棵二叉树，判断该二叉树是否是平衡二叉树。
在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树
平衡二叉树：所有节点的左右子树的高度差小于1的二叉树。

/*struct TreeNode
{
    int data;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int val) :data(val), left(NULL), right(NULL) {}
};
*/
class Solution {
public:
    bool IsBalanced_Solution(TreeNode* pRoot) {
        if (pRoot == NULL) {
            return true;
        }
        if (abs(getTreeDeep(pRoot->left) - getTreeDeep(pRoot->right)) <= 1) {
            return true;
        }

        return false;

    }
    //单个子树的高度
    int getTreeDeep(TreeNode* pRoot) {
        if (pRoot == NULL) {
            return 0;
        }
        int left = getTreeDeep(pRoot->left);
        int right = getTreeDeep(pRoot->right);
        return 1 + max(left, right);
    }
};