改进计算二叉树中节点值最大和的函数的运行时间

Improve runtime of function calculating maximum sum of node values in a binary tree

本文关键字：和的 函数 运行时间 计算 二叉树 节点      更新时间：2023-09-26

其思想是找到值最大的路径（沿该路径的节点值的总和）。编辑：节点是完全无序的，这意味着你必须搜索整个路径，以知道一个路径是否比另一个路径有更大的值。

这是树的节点构造函数：

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层深的树，它只会很快（在一秒内）返回一个答案。我试图为一棵100级深的树找到最大和路径，但似乎找不到我的路。有没有改善运行时间的方法？

答案不好，因为我没有完全理解问题
若树的数据是静态的，则可以存储从根到顶点的预先计算的和。

下一次尝试
尝试删除递归
但我认为它不会更快，因为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
相关文章：