performance - 找出二叉树是否平衡或效率不高

Question

如果一棵二叉树的左子树和右子树都是平衡的，并且左子树和右子树的高度之差小于等于，则称二叉树是高度平衡的到 1。

我必须找出给定的二叉树是否平衡!

基于上述概念，我使用了以下代码:

bool isbalanced(struct node *root)
{
    int left,right;
    if(root==NULL)
    return true;
    else
    {
        left=height(root->left);
        right=height(root->right);
        if(abs(left-right)<=1 && isbalanced(root->right)==true && isbalanced(root->left)==true)
        return true;
        else
        {
            return false;
        }
    }
}

我使用单独的 height() 函数计算了高度:

int height(struct node *root)
{
    if(root==NULL)
    return 0;
    int left=height(root->left);
    int right=height(root->right);
    if(left>right)
    return 1+left;
    else
    return 1+right;
}

无论树是平衡的还是不平衡的，我都会得到正确的解决方案。但是，如果给定的树是倾斜的，则时间复杂度将为 O(n^2)。

有没有一种方法可以让我以更有效的方式完成这项任务？

Answer 1

将给定树视为有根树，我们可以通过对给定树进行一次深度优先搜索来计算所有节点的高度。拟议解决方案的草图:

int isbalanced(struct node *root)
{
    int left,right;
    if(root==NULL)
    return 0;
    else 
    {
        left=isbalanced(root->left);
        right=isbalanced(root->right);
        if(left==-1||right==-1||fabs(left-right)>1){
          return -1;  // it indicates the tree rooted at root or below is imbalanced
        }else{
          return max(right,left)+1;
        }
    }
}

如果上述函数返回 -1，则树不平衡，否则平衡。它不需要高度函数。

运行时间:O(V+E)

请注意:代码未经测试