124. 二叉树中的最大路径和

难度：🔴 Hard | 标签：树、DFS | 状态：⬜ LeetCode 链接

思路

每个节点：

• 返回值：以本节点为端点向下的最大单边贡献 = max(0, max(left, right)) + val
• 答案：经过本节点的最长路径 = left + right + val

负贡献裁剪：单边 < 0 时取 0（不选这一支）。

代码

class Solution {
    int best = INT_MIN;
    int dfs(TreeNode* r) {
        if (!r) return 0;
        int l = max(0, dfs(r->left));
        int rt = max(0, dfs(r->right));
        best = max(best, l + rt + r->val);
        return max(l, rt) + r->val;
    }
public:
    int maxPathSum(TreeNode* root) {
        dfs(root);
        return best;
    }
};

复杂度

• 时间 O(n)，空间 O(h)

易错 / 回顾

• best 初始 INT_MIN（节点值可能全负）
• 返回值是”单边”，更新答案是”双边”——两套不要混
• 单边贡献用 max(0, ...) 裁掉负数