LeetCode:Balanced Binary Tree

LeetCode:Balanced Binary Tree

題目描述：

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

思路：當樹的左子樹的高度與右子樹的高度相差小於一，且左右子樹各自都為平衡二叉樹時，樹為平衡二叉樹。

代碼：

bool Solution::isBalanced(TreeNode *root)
{
    if(root == NULL)
        return true;
    if(abs(treeHeight(root->left) - treeHeight(root->right)) > 1)
        return false;
    return isBalanced(root->left) && isBalanced(root->right);
}

int max(int a,int b)
{
    return a > b ? a : b;
}

int Solution::treeHeight(TreeNode * root)
{
    if(root == NULL)
        return 0;
    return max(treeHeight(root->left),treeHeight(root->right)) + 1;
}