【原】判断一个给定二叉树是否是平衡二叉树

方法一：

//求当前节点的高度

int level(TreeNode *root)

{

    if(root == NULL) return 0;

    return 1 + max(level(root->left),level(root->right));

}

bool isBalanced(TreeNode *root)

{

    if(root == NULL)    return true;

    int factor = abs(level(root->left) - level(root->right));

    return factor < 2 && isBalanced(root->left) && isBalanced(root->right);

}

方法二：一种更好的方法

isBalanced返回当前节点的高度，-1代表树不是平衡二叉树，将计算结果自底向上传递，并且确保每个节点只计算一次，复杂度为O(n)。

int isBalancedHelper(TreeNode *root)

{

    if(root == NULL) return 0;

    int Lh = isBalancedHelper(root->left);

    if(Lh == -1)     return -1;

    int Rh = isBalancedHelper(root->right);

    if(Rh == -1)    return -1;

    if(abs(Lh - Rh) > 1)    return -1;

    return max(Lh,Rh) + 1;

}

bool isBalancedTree(TreeNode *root)

{

    if(root == NULL)    return true;

    return (isBalancedHelper(root) != -1);

}