未通过所有测试用例的二叉树的最大路径

Question

我正试图解决这个Leetcode问题:二叉树最大路径和。我知道这个问题有很多SO的答案。但是我找不到任何与我的问题相关的东西。因此，在深入研究代码之前，我想对如何编写算法进行一个高层次的概述。

If I am at a particular node, I considered the following cases.
Case 1: The maximum path is somewhere inside the left subtree (not including the current node)
Case 2: The maximum path is somewhere inside the right subtree (not including the current node)
Case 3: The maximum path starts from the current node and ends somewhere in the left subtree
Case 4: The maximum path starts from the current node and ends somewhere in the right subtree
Case 5: The maximum path is the current node itself.
Case 6: The maximum path starts somewhere in the left subtree, goes through the current node, and ends somewhere in the right subtree.

代码如下:

var maxPathSum = function(root) {
if (root.left === null && root.right === null) {
return root.val;
}

// Case 1: Max sum is in the left subtree (not including the root)
let leftPathSum = 0;
if (root.left) {
leftPathSum = maxPathSum(root.left);
}
// Case 2: Max sum is in the right subtree (not including the root)
let rightPathSum = 0;
if (root.right) {
rightPathSum = maxPathSum(root.right);
}


// Case 3: root + leftPathSum
let leftSumWithRoot = leftPathSum + root.val; 
// Case 4: root + rightPathSum
let rightSumWithRoot = rightPathSum + root.val; 

let maxWithRoot = Math.max(leftSumWithRoot, rightSumWithRoot); 
let maxWithoutRoot = Math.max(leftPathSum, rightPathSum); 

let maxSoFar = Math.max(maxWithRoot, maxWithoutRoot); 

// Case 5: Root with alone
maxSoFar = Math.max(maxSoFar, root.val); 

// Case 6: Max path goes through the root
let maxThroughRoot = leftSumWithRoot + rightSumWithRoot - root.val;

return Math.max(maxThroughRoot, maxSoFar);

};

我得到一些通过的测试用例，有些没有，特别是那些有负值的。我知道我的算法很可能有问题，但有人能帮我在哪里我的想法走错了方向。我看到了解决这个问题的不同方法。在一些解决方案中，它们比较maxPathSum(节点)。(左)和maxPathSum(node.right)与0这个问题与此有关吗?此外，在其他一些解决方案中，它们不考虑位于左右子树中的maxPathSum。我不应该这么做吗?如果有人能告诉我我哪里做错了，我会非常感激。提前谢谢。

Answer 1

您的代码在此输入中失败:[-2,-1]

图形如下:

-2
/
-1

所以let maxWithoutRoot = Math.max(leftPathSum, rightPathSum);等于0。那么maxSoFar将为0，所以最终输出为0。如果我组织你的代码:

var maxPathSum = function(root) {
let res=root.val
function dfs(node){
if (node===null){
return 0
}
let left=dfs(node.left)
let right=dfs(node.right)
// ignoring negatives. looking for max, so if left or right is negative, do not add it
let leftMax=Math.max(left,0)
let rightMax=Math.max(right,0)
res=Math.max(node.val+leftMax+rightMax,res)
return node.val+Math.max(leftMax,rightMax)
}
dfs(root)
return res
};