0

如果二叉树的左子树和右子树都是平衡的，并且左子树和右子树的高度之差小于或等于 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)。

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

4

2 回答 2

3

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

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)

请注意：代码未经测试

于 2013-07-07T19:47:08.877 回答
1

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

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

1 簿记细节留给读者练习

于 2013-07-07T19:42:27.763 回答