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

maxpathsum不能直接返回子树最大路径和，因为路径不可分叉：dfs需返回单边最大收益以供父节点拼接，同时用临时变量计算跨左右的完整路径和并更新全局最大值。

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

为什么 `maxPathSum` 不能直接返回子树最大路径和？

因为路径在二叉树中是「不拐弯」的：从某节点出发，向下延伸到左右子树中的至多一个分支（否则就分叉了，不是一条路径）。但全局最大路径可能横跨根节点——左子树→根→右子树。所以每个节点要算两件事：以该节点为顶点的完整路径和（可跨左右），以及以该节点为起点向下延伸的最大单边路径和（只能选左或右，用于父节点拼接）。后者就是「节点收益」，必须非负才值得向上贡献；负值直接截断，用 0 替代。

`dfs` 函数必须返回单边最大收益，而非全局最大值

这是递归设计最关键的约束。如果让 dfs 返回经过当前节点的最大路径和，父节点就无法安全拼接——它不知道你返回的值是否已包含左右子树，会导致重复计算或路径分叉。正确做法是：

dfs(node) 只负责计算并返回「能向上贡献的单边最大收益」：node->val + max(0, dfs(node->left), dfs(node->right))
在每次进入 dfs 时，用临时变量计算「以 node 为顶点的完整路径和」：node->val + max(0, left_gain) + max(0, right_gain)，并持续更新全局答案 max_sum
空节点返回 0，表示无收益；叶子节点返回自身值（若为负，上层会截断）

负值节点如何处理？`max(0, ...)` 不是凭空加的

这个 max(0, ...) 是路径连续性的硬性要求。比如左子树最大单边收益是 -5，意味着从左子树往下走只会拉低总和，那不如「不走左边」，即把左贡献视为 0。同理对右子树。但注意：node->val 本身不能被跳过——路径至少包含当前节点。所以实际拼接逻辑是：

C++14

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

下载

int left_gain = max(0, dfs(node->left));
int right_gain = max(0, dfs(node->right));
int price_newpath = node->val + left_gain + right_gain; // 当前节点为顶点的完整路径
max_sum = max(max_sum, price_newpath);
return node->val + max(left_gain, right_gain); // 向上只传单边最大收益