问题描述:

I am trying to find the sum and average of data of type int from a longest path of a BST. I've made the following functions :

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;

}

The function longest returns me the sum of the data, but how to return its average without traversing the tree again in order to figure out how many nodes are in the longest path?

EDIT: The prototype of private function longest has to be int longest(node* root) and it has to return the average or at least the sum of the elements to the public function so it can return the average knowing the sum

网友答案:

Your code is not optimized. Unnecessary repeating the traversal is never recommended. You can use the given below function. It will do the task in O(n) time, where n is the number of nodes in binary tree.

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);
}

find the sum and average of data of type int from a longest path of a BST

sum = longestPathSum;

average = longestPathSum / maxHeight;

网友答案:

Instead of function 'longest' returning the sum of weights, you can pass the sum of weights and height as reference. This will allow not traversing the BST twice.

相关阅读:
Top