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

Question

二叉树被称为高度平衡，如果它的左子树

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

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

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

您正在遍历左右子树两次：一次是为了获得它们的高度，另一次是为了测试它们是否平衡。通过使用同时包含高度和平衡标志的结构，将一个结构向下传递以由左侧子树填充，另一个结构由右侧子树填充，可以消除一半的工作。

然后，通过在扫描右侧时使用左侧子树中的信息（反之亦然），您可以进一步改进这一点。在许多情况下，在整个树不平衡但每个子树都平衡的情况下，可以使用左子树信息（使用适当的簿记¹）来早期切断右子树搜索。

¹_{簿记细节留给读者作为练习}

Answer 2

将给定的树视为根树，我们可以通过给定树上的单个深度优先搜索来计算所有节点的高度。建议的解决方案草图：

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）

请注意：代码未测试