如何通过递归算法优化二叉树最大路径和，实现节点收益最大化实战技巧？

本文共计948个文字，预计阅读时间需要4分钟。

节点收益并非标准术语，而是解题时人为定义的中间量：

关键区分点：

• node_gain 是递归返回值，用于供父节点计算自己的收益
• 全局最大值 max_sum 才是题目要的答案，它可能来自某个节点的“左+自己+右”

所以递归函数干两件事：更新全局最大值、返回当前节点的最大单向收益。

递归函数怎么写？maxPathSum 和 gain 分开才不乱

不要试图在一个函数里既更新答案又返回值。推荐拆成两个逻辑：

立即学习“C++免费学习笔记（深入）”；

• 主函数 maxPathSum 初始化全局变量，调用递归入口
• 辅助函数 maxGain（或叫 dfs）只做一件事：返回以当前节点为起点的最大单向路径和

注意几个细节：

- maxGain 中，若子树收益为负，直接舍弃（用 max(0, left_gain)） - 当前节点的完整路径和是 root->val + left_gain + right_gain，这个值用来更新全局最大值 - maxGain 的返回值只能是 root->val + max(left_gain, right_gain)，因为单向路径不能分叉

int maxGain(TreeNode* node) { if (!node) return 0; int left_gain = max(0, maxGain(node->left)); int right_gain = max(0, maxGain(node->right)); max_sum = max(max_sum, node->val + left_gain + right_gain); return node->val + max(left_gain, right_gain); }

空节点、负数、单节点这些边界怎么处理？

• 空节点返回 0，不是 INT_MIN —— 因为我们定义的是“收益”，不走这条路径就当没贡献，而不是拖累
• 节点值为负时，max(0, ...) 会自然让负子树被剪枝，但当前节点本身可能成为答案（比如全负树，答案就是最大的那个负数）
• 单节点树：left_gain 和 right_gain 都是 0，所以 max_sum 更新为 node->val，返回值也是 node->val

常见错误：

- 把空节点返回值设成 INT_MIN，导致 node->val + INT_MIN 溢出或逻辑错乱 - 忘记在更新 max_sum 前对左右收益取 max(0, ...)，结果把负子树强行拉进来 - 在返回值里也加了 max(0, ...)，导致本该传递负值（如当前节点是 -5，左子是 -10，右子是 null）时返回 0，丢失了 “-5 本身” 这条合法路径

为什么不能直接用 maxPathSum 自己递归？

因为 maxPathSum 的语义是“整棵树的最大路径和”，而递归过程中你需要的是“从某节点往下走的最大单向和”。如果硬用同一个函数，返回值含义会模糊：有时代表答案，有时又要当子问题结果用，极易混淆。

更实际的问题是：你无法在不引入额外状态的情况下，在一次遍历中同时维护两个不同定义的极值。用一个辅助函数隔离职责，代码可读性和调试成本都低得多。

全局变量 max_sum 初始化成 INT_MIN 是必要的，否则全负树会出错；但所有子调用中参与加法的收益项，一律按“可弃权”处理（即 max(0, x)），这是收益模型成立的前提。