二叉树最大路径和算法无法通过含负数测试用例问题求助

问题核心缺陷分析 #

1. 递归返回值的定义混淆 #

这是最根本的逻辑错误：
你现在写的maxPathSum函数返回值是「当前子树内部的最大路径和」，这个值对应的路径可能是跨左右子树的V型结构，这类路径存在分叉，无法和当前节点的父节点拼接。你后续计算leftSumWithRoot（根+左子树路径）时，直接把左子树的全局最大路径和加当前节点值，相当于强行拼接了一个分叉的非法路径，自然会得到错误结果。

正确的递归设计需要拆分两个逻辑：

• 单独维护一个全局变量，存储遍历过程中所有合法路径的最大和（包含子树内部V型、单臂、单个节点等所有情况）
• 递归函数的返回值是「以当前节点为端点，向下延伸的最大单臂路径和」，这个值是专门用来给父节点拼接用的，只能是单链结构，不能有分叉。

2. 负数场景处理错误 #

你目前的代码里有两个负数相关的问题：

• 初始leftPathSum、rightPathSum设为0，当子树不存在时相当于默认贡献0，这部分逻辑没问题，但如果子树存在但返回的单臂和是负数，你没有做舍弃处理
• 当子树的单臂贡献为负时，强行拼接会拉低当前节点的总路径和，此时应该直接舍弃该子树（相当于该子树贡献为0，只取当前节点本身），这就是你看到的其他解法里「和0比较」操作的作用。

关于是否保留子树内部最大路径逻辑的说明 #

需要保留，但是不能把这个逻辑的结果作为递归返回值给上层使用，它只用来更新全局最大路径和变量即可。

修正后的实现代码 #

var maxPathSum = function(root) {
    let maxSum = -Infinity; // 全局存储最大路径和

    // 递归函数返回值：以当前节点为端点的向下延伸的最大单臂路径和
    const dfs = (node) => {
        if (!node) return 0;
        // 左右子树的单臂贡献，负数直接舍弃（取0）
        const leftGain = Math.max(dfs(node.left), 0);
        const rightGain = Math.max(dfs(node.right), 0);

        // 计算当前节点作为顶点的V型路径和，更新全局最大值
        const currentVPathSum = node.val + leftGain + rightGain;
        maxSum = Math.max(maxSum, currentVPathSum);

        // 返回给上层的单臂和，只能选左右其中一条路径延伸
        return node.val + Math.max(leftGain, rightGain);
    }

    dfs(root);
    return maxSum;
};

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