为何最大路径和算法中要排除负数？求逻辑合理性解析

先看完整的算法代码：

export function maxPathSum(tree: BinaryTree): number {
  let currMax = -Infinity; 

  const helper = (node: BinaryTree | null): number => {
    if (!node) return 0; 

    const leftVal = Math.max(helper(node.left), 0); 
    const rightVal = Math.max(helper(node.right), 0); 

    currMax = Math.max(leftVal + rightVal + node.value, currMax); 

    return Math.max(leftVal, rightVal) + node.value; 
  }

  helper(tree); 

  return currMax; 
}

你疑惑的点在于“排除负数会不会导致错误总和”，其实这行代码的逻辑完全正确，核心要搞清楚两个关键点：

1. helper函数的职责不是计算子树的最大路径和 #

helper返回的是以当前节点为起点，向下延伸（只能选左或右其中一条分支）的最大路径和。这个值是给当前节点的父节点用的——父节点如果要把当前节点纳入自己的路径，只能选当前节点的左/右一条链（因为路径不能分叉，节点只能经过一次）。

2. 和0取max的意义：避免负贡献拉低总和 #

如果某个子树的helper返回值是负数，说明从当前节点往这个子树走，只会让路径和变小。这时候父节点完全可以放弃这个分支，相当于这个分支对当前节点的贡献是0（只取当前节点自己的值）。

举两个实际例子：

• 假设当前节点值为3，左子树的helper返回-2，右子树返回-1：
  leftVal取0，rightVal取0，currMax计算为3+0+0=3（对应单节点路径），helper返回3+0=3（父节点可以选择把这个节点作为路径的一部分）。如果不取0直接用负数，currMax会变成3+(-2)+(-1)=0，这显然错误，因为单节点3的路径和更大。
• 假设当前节点值为5，左子树helper返回2，右子树返回-3：
  leftVal取2，rightVal取0，currMax计算为5+2+0=7（对应左子树-当前节点的路径），helper返回5+2=7（父节点可以把这条链加入自己的路径）。如果不取0用-3，currMax会是5+2+(-3)=4，比7小，反而漏掉了更优的路径。

3. 真正的最大路径和由currMax记录 #

currMax会在每个节点计算以该节点为顶点的完整路径和（左分支+当前节点+右分支），即使左右分支都是负数，Math.max也会自动保留当前节点的值（因为0+0+node.value比负数加起来更大），不会漏掉单节点这种合法路径。

所以这行代码的逻辑是在给父节点提供最优的分支选择，同时保证currMax能记录所有可能的最大路径情况，完全不会导致错误总和。

内容的提问来源于stack exchange，提问作者J Seabolt