C++ 实现二叉树最大路径和递归核心逻辑 _ 节点收益最大化【实战】-C++-PHP中文网

maxPathSum必须拆成两个函数：dfs返回以当前节点为起点的单边最大收益，用于父节点拼接；全局变量max_sum在dfs中实时更新经过该节点的双边路径和，避免混用导致路径分叉或重复计算。

c++ 实现二叉树最大路径和递归核心逻辑 _ 节点收益最大化【实战】

最大路径和不是“从根到叶子的最长路径”，而是任意节点出发、可拐弯、不重复经过节点的路径上所有节点值之和的最大值；递归函数必须返回“以当前节点为起点向下延伸的单边最大收益”，而不是整棵树的答案。

为什么 `maxPathSum` 必须拆成两个函数？

因为递归过程中要同时解决两个不同目标：

向上返回：以当前节点为“路径顶端”，只能往左或右走一步，能带给父节点的最大贡献值（即 node->val + max(0, left_gain, right_gain)）
全局更新：当前节点作为路径“中转点”，左右子树收益都可取（即 node->val + max(0, left_gain) + max(0, right_gain)），这个值可能成为最终答案，但不能返回给父节点

混用会导致逻辑错乱——比如错误地把带左右分支的和传上去，父节点再拼接就会重复计算或路径分叉。

`dfs` 函数的返回值定义与边界处理

dfs 的语义是：“我能为父节点提供的最大单向路径收益”，所以：

C++14

C++14 对 C++11 的修正与增强版本，适合旧系统维护和较老工具链兼容。

下载

空节点返回 0（不是 INT_MIN，否则 max(0, left_gain) 就失效了）
负收益子树直接舍弃，用 max(0, ...) 截断，因为加上它只会拉低总和
返回值恒为 node->val + max(0, left_gain, right_gain)，确保路径连续且只向下延伸一次

示例片段：

int dfs(TreeNode* node) {
    if (!node) return 0;
    int left_gain = max(0, dfs(node->left));
    int right_gain = max(0, dfs(node->right));
    // 全局更新：此处允许左右都取
    max_sum = max(max_sum, node->val + left_gain + right_gain);
    // 向上返回：只选一边
    return node->val + max(left_gain, right_gain);
}