BST的最長路徑的平均值

我想從BST的最長路徑中找到類型爲int的數據的總和和平均值。我做了以下功能：BST的最長路徑的平均值

int table::longest(){ 
    return longest(root); 
} 

int table::longest(node* curr){ 
    int suml = 0; 
    int sumr = 0; 

    if(!curr) 
     return 0; 
    int hleft = height(curr->left); 
    int hright = height(curr->right); 
    if(hleft > hright){ 
     suml = curr->data; 
     return suml += longest(curr->left); 
    } 
    sumr = curr->data; 
    return sumr += longest(curr->right); 
} 

int table::height(node* curr){ 
    if(!curr) 
     return 0; 
    int hLeft = 1 + height(curr->left); 
    int hRight = 1 + height(curr->right); 

    if(hLeft > hRight) 
     return hLeft; 
    return hRight; 
}

longest返回我的數據和功能，但如何在不再次依次遍歷樹返回其平均找出多少個節點都在最長路徑？

編輯：私有函數longest的原型必須是int longest(node* root)它具有的元素的平均或至少總和返回公共職能，因此它可以返回平均知道總和

來源

2016-08-07 Mr.SrJenea

您已經遍歷了兩次（實際上，'N'次，其中'N'是樹的深度 - 您的算法在深度上是二次的）。 'height'自己遍歷。你需要一個單一的函數，將高度和權重的總和一起返回 - 這將最大限度地減少工作量。 –

@IgorTandetnik：我如何才能做到具有給定的函數原型？ –

編寫一個具有不同原型的助手函數，從這個函數中調用它。 –

您的代碼未優化。從不建議不必要的重複遍歷。你可以使用下面給出的函數。它將在O（n）時間完成任務，其中n是二叉樹中的節點數。

int maxHeight = 0; 
int longestPathSum = 0; 

int table::longest(){ 
    longest(root, 0, 0); 
    return longestPathSum; 
} 

void table::longest(node* curr, int sum, int height){ 
    if(curr == NULL) return 0; 
    sum += curr->data; 
    if(++height > maxHeight) { 
     maxHeight = height; 
     longestPathSum = sum; 
    }  
    longest(curr->left, sum, height); 
    longest(curr->right, sum, height); 
}

查找從BST

總和= longestPathSum的最長路徑的總和和int類型的數據的平均值;

average = longestPathSum/maxHeight;

來源

2016-08-07 05:21:57

問題是我的函數'longest'必須是'int longest（node * root）'的形式。我無法改變它，它必須返回平均值。或者至少返回總和和公共函數「最長」來返回知道總和的平均值 –

代替函數'最長'返回權重的總和，您可以傳遞權重和高度之和作爲參考。這將不允許兩次遍歷BST。

來源

2016-08-07 02:03:34 Sandeep

最長的功能必須如此。這是問題的要求 –

BST的最長路徑的平均值

回答

相關問題