最大路径和需用全局变量实时更新,因跨子树路径无法通过递归返回值传递;maxgain必须返回单侧最大贡献,语义为“从当前节点向下走一条路的最大和”,空节点返回0,截断负贡献后立即更新全局最大值。

最大路径和不能靠递归函数返回值直接得到,必须用全局变量或引用在每个节点处实时更新 left_gain + right_gain + root->val;否则像 15 → 20 → 7 这种跨左右子树的路径会彻底丢失。
为什么 maxGain() 必须只返回单侧贡献
路径定义要求节点至多出现一次、不可分叉。父节点调用 maxGain(root->left) 时,拿到的值要能安全加到自己的路径里——如果这个值本身已含左右子树(即分叉了),父节点再拼接就违法。
-
maxGain的语义必须严格是:“从当前节点出发、向下走一条路(左或右)的最大和” - 正确返回写法:
return root->val + std::max({0, left_gain, right_gain}) - 错误写法:
return root->val + left_gain + right_gain—— 这会让上层误以为可以同时接两边 - 即使
root->val是负数(如 -10),而左右收益是 8 和 9,也只取-10 + std::max(0, 8, 9) == -1,不是7
max_sum 更新必须在获取截断后收益的瞬间完成
最大路径不一定经过根,可能藏在任意中间节点作为顶点。更新时机错一点,整个解就偏了。
- 先调用:
int left_gain = maxGain(node->left)、int right_gain = maxGain(node->right) - 立刻截断:
int l = std::max(0, left_gain)、int r = std::max(0, right_gain) - 立刻更新:
max_sum = std::max(max_sum, node->val + l + r) - 错误做法:用原始
left_gain和right_gain直接算和再更新——若它们是 -5 和 -8,结果就被拖垮
空节点必须返回 0,不是 INT_MIN 或 -1
空节点语义是“无贡献”,不是“灾难性拖累”。返回 INT_MIN 会导致加法溢出,max(0, INT_MIN) 在部分平台行为未定义,更重要的是破坏了截断逻辑的直觉一致性。
- 所有递归入口第一行必须写:
if (!root) return 0;,否则访问root->left会崩溃 - 叶子节点场景下,左右都是空,
l == r == 0,node->val + 0 + 0自然把该节点值记入max_sum - 全负树如
[-3,-2,-1]中,每层截断后只剩node->val参与更新,首次非空节点即可确立初始最大值 -
max_sum初始化必须是INT_MIN,不是0或root->val;否则输入[-3]会返回0
真正容易被忽略的是:同一个子树收益,在两个上下文里处理方式不同——向上交能力时舍弃负值,本地拼完整路径时仍要用原始值(再套 std::max(0, ))。漏掉任一环节,比如只在返回值里截断却在 lmr 计算中仍用原始负值,结果就错了。
C++免费学习笔记(深入):立即使用
在学习笔记中,你将探索 C++ 的入门与实战技巧!











