Durchschnitt des längsten Pfades eines BST

Question

Ich versuche die Summe und den Durchschnitt der Daten vom Typ int aus einem längsten Pfad eines BST zu finden. Ich habe folgende Funktionen aus:

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

Die Funktion longest mir die Summe der Daten zurückgibt, aber wie seine durchschnittlichen zurückzukehren, ohne den Baum wieder in Ordnung zu durchlaufen, wie viele Knoten in dem längsten Weg ist, um herauszufinden, ?

EDIT: Der Prototyp der privaten Funktion longest hat int longest(node* root) sein, und es hat den Durchschnitt oder zumindest die Summe der Elemente der Öffentlichkeit Funktion zurückzukehren, damit es die durchschnittliche wissen die Summe zurückgeben kann

Answer 1

Ihr Code ist nicht optimiert. Unnötiges Wiederholen der Traversierung wird niemals empfohlen. Sie können die unten angegebene Funktion verwenden. Es wird die Aufgabe in O (n) Zeit erledigen, wobei n die Anzahl der Knoten im Binärbaum ist.

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

die Summe und die durchschnittliche Daten des Typs int aus einem längsten Pfad eines

= sum

BST finden longestPathSum;

Durchschnitt = lonestPathSum/maxHeight;

Answer 2

statt Funktion 'längste' die Summe der Gewichte zurückgeben, können Sie die Summe aus Gewichten und Höhe als Referenz übergeben. Dies ermöglicht es, das BST nicht zweimal zu durchlaufen.