バイナリツリーのノード値の最大合計を計算する関数の実行時間を改善する

Question

考えられるのは、値が最大のパス（このパスに沿ったノードの値の合計）を見つけることです。編集：ノードは完全に順序付けられていません。つまり、あるパスが別のパスよりも大きな値を持つかどうかを知るためには、パス全体を検索する必要があります。ここで

は、ツリーのノード・コンストラクターである：ここで

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

は、パスの最大値を計算する関数です。

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

機能はかなり非効率的であり、唯一の合理的な答えを返します。約25レベル深い樹木では速い（1秒以内）。私は100レベルの深さのツリーのための最大の和のパスを見つけるしようとしている、そこに自分の道を見つけることができないようです。ランタイムを向上させる方法はありますか？

Answer 1

悪い答え、私は完全に
に疑問を理解していないので、あなたは木のデータが静的である場合には頂点にルートから予め計算された合計を保存することができます。

---

次の試み
再帰を削除してください。
しかし、私はV8がすでにあなたのコードを最適化しているので速くないと思います。

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

---

次！

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