dfs函数必须只返回单边最大贡献,因路径不可分叉;全局变量实时更新“左+根+右”和,确保跨子树路径不丢失。

最大路径和必须用两个逻辑并行推进:递归函数只返回单边最大贡献,全局变量(或引用)实时捕获“左+根+右”路径和;混用返回值和答案会导致 15→20→7 这类跨子树路径完全丢失。
为什么 dfs 函数必须只返回单边最大贡献
路径定义要求节点不重复、不可分叉——父节点只能接左或右其中一支,不能同时接两边再往上送。所以 dfs 的唯一职责是告诉父节点:“如果走我这条线,最多能加多少”。
- 返回值语义必须严格为:
node->val + max(0, left_gain, right_gain),负子树直接归零 - 若错误返回
node->val + left_gain + right_gain,父节点再拼接就会形成 Y 形路径,违反定义 - 哪怕当前节点值是 -10、左右子树贡献分别是 8 和 9,
dfs也只能返回 -10 + max(0, 8, 9) = -1,不是 -10 + 8 + 9 = 7
max_sum 更新必须在递归体内部、左右调用之后立即执行
最大路径不一定经过根,可能藏在任意中间节点作为顶点。更新时机错一点,整个解就偏了。
- 正确位置:获取
left_gain和right_gain后,立刻算node->val + max(0, left_gain) + max(0, right_gain)并更新max_sum - 错误做法:在函数入口初始化
max_sum,或等所有递归结束再扫一遍——漏掉中间节点的拐点路径 - 初始化必须是
INT_MIN,不是0或root->val;否则输入[-3]会返回0
空节点返回 0 是安全且必要的设计
这不是随意选的占位符,而是让 max(0, gain) 截断逻辑自然生效的关键支点。
立即学习“C++免费学习笔记(深入)”;
- 若空节点返回
INT_MIN,max(0, INT_MIN)在多数平台仍是0,但语义混乱,且有溢出风险 - 若漏写
if (!node) return 0;,后续访问node->left直接崩溃 - 叶节点场景下,左右都是空,
left_gain = right_gain = 0,此时node->val + 0 + 0就是它自身的候选路径和
负值子树要“截断上传”,但不能“丢弃参与”
同一个子树收益,在两个上下文里处理方式不同:向上交能力时舍弃负值,本地拼完整路径时仍要用原始值(再套 max(0, ))。
- 错误写法:
int left_gain = dfs(node->left); int right_gain = dfs(node->right);然后直接拿原始负值去算node->val + left_gain + right_gain—— 路径和被拖垮 - 正确写法:先得原始值,再各自
max(0, left_gain)和max(0, right_gain),然后用于两处:
– 更新max_sum:用这两个截断后的值
– 返回值:用node->val + max(left_gain截断后, right_gain截断后) - 真正容易被忽略的是:你手里始终只有两个数(左、右),却要同时完成“选一个交上去”和“两个全拿来拼一次”的动作——这个割裂感,就是调试时最卡壳的地方


















