Verbesserung der Laufzeit der Funktion Berechnung der maximalen Summe der Knotenwerte in einem Binärbaum

Question

Die Idee besteht darin, den Pfad zu finden, dessen Wert am größten ist (die Summe der Werte der Knoten auf diesem Pfad). EDIT: Die Knoten sind völlig ungeordnet, was bedeutet, dass Sie den gesamten Pfad durchsuchen müssen, um zu wissen, ob ein Pfad einen größeren Wert als ein anderer hat. Hier

ist der Knoten Konstruktor des Baumes:

var Node = function(val) { 
    this.val = val; 
    this.left = null; 
    this.right = null; 
} 

Hier wird die Funktion den Maximalwert von Pfaden Berechnung:

function maxPath(top) { 
    if (top.right === null || top.left === null) return top.val; 
    return Math.max(top.val, Math.max(top.val + maxPath(top.left), top.val + maxPath(top.right))); 
} 

Die Funktion ziemlich ineffizient ist und nur eine Antwort zurückgeben vernünftigerweise schnell (innerhalb einer Sekunde) für einen Baum, der ungefähr ~ 25 Level tief ist. Ich versuche, den maximalen Summenpfad für einen Baum zu finden, der 100 Stufen tief ist, scheint nicht meinen Weg dorthin zu finden. Gibt es eine Möglichkeit, die Laufzeit zu verbessern?

Answer 1

Bad Antwort, weil ich nicht in vollem Umfang in Frage verstehe
Sie vorberechnete Summe von der Wurzel speichern kann nach Knoten, wenn Daten von Baum statisch sind.

---

nächste Versuch
Versuchen Rekursion entfernen.
Aber ich denke, es ist nicht schneller, weil V8 bereits Ihren Code optimieren.

function getMaxPath (topNode) { 
    var node = topNode; 
    var sum = node.val; 
    while (node.right) { // binary tree, right? So rigth and left exists together. 
     node = (node.right.val >= node.left.val) ? node.right : node.left; 
     sum = node.val; 
    } 
    return sum; 
} 

---

Next!

var sums = []; // array of sum for each leaf 
topNode.sum = topNode.val; 

function fall(node) { 
    if (!node.right) 
     return sums.push(node.sum); 

    node.right.sum = node.sum + node.right.val; 
    fall(node.right); 

    node.left.sum = node.sum + node.left.val; 
    fall(node.left); 
} 

fall(topNode); 
console.log(Math.max.apply(Math, sums)); // find max