LeetCode 124.二叉树最大路径和：单负节点测试用例错误排查

错误原因分析 #

你之前的代码用max(0, 递归结果)来排除负节点贡献，同时全局最大路径和可能初始化为0，这就导致单个负节点的场景下，递归返回0，全局最大取0而非节点本身的负值，不符合预期。

核心修改方案 #

1. 调整递归返回逻辑 #

递归函数要返回以当前节点为起点向下延伸的最大路径和，这个值允许为负数（当当前节点本身是负数且左右子树贡献都为负时，只能选当前节点）。所以不能直接和0取最大，而是返回当前节点值 + max(左右子树贡献, 0)——这里加0的意思是，如果子树贡献为负，就不选该子树，只保留当前节点。

2. 修正全局最大初始值 #

不能把全局最大初始化为0，因为当所有节点都是负数时，最大路径和就是最大的那个负数。正确做法是将全局最大初始化为根节点的值，或者Integer.MIN_VALUE，再在递归中更新。

修正后的Java代码 #

class Solution {
    private int maxSum;

    public int maxPathSum(TreeNode root) {
        maxSum = root.val; // 初始化为根节点值，覆盖单负节点场景
        dfs(root);
        return maxSum;
    }

    private int dfs(TreeNode node) {
        if (node == null) {
            return 0; // 空节点贡献为0
        }

        // 计算左右子树的有效贡献，负贡献直接取0（不选该子树）
        int leftContribution = Math.max(dfs(node.left), 0);
        int rightContribution = Math.max(dfs(node.right), 0);

        // 更新全局最大路径和：当前节点作为路径顶点的总和
        int currentPathSum = node.val + leftContribution + rightContribution;
        maxSum = Math.max(maxSum, currentPathSum);

        // 返回当前节点能向上提供的最大贡献（只能选左或右子树的一条路径）
        return node.val + Math.max(leftContribution, rightContribution);
    }
}

代码说明 #

• 单个-3节点场景：dfs(-3)中左右贡献都是0，currentPathSum = -3 + 0 + 0 = -3，maxSum初始为-3，最终返回-3，符合预期。
• 混合节点场景：leftContribution和rightContribution会自动过滤负贡献的子树，全局最大会正确记录所有可能的路径和。

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