牛客125题解：二叉树最大路径和的动态规划解法
2天前
一、题目解读
牛客125题要求求解一棵二叉树中节点之间的最大路径和。路径定义为任意两个节点之间的连通路径（无需经过根节点），节点值可正可负。核心在于找到包含节点值之和最大的路径，需考虑子树贡献与全局最优解的权衡。
二、解题思路
1. 后序遍历：通过递归遍历二叉树，自底向上计算每个节点的贡献；
2. 动态规划：维护两个值：
○ 当前节点为路径起点的最大路径和（需包含左右子树中较大的贡献）；
○ 全局最大路径和（更新所有可能路径中的最大值）；
3. 处理负数：若子树贡献为负，则舍弃该子树，避免影响整体路径和。
三、解题步骤
1. 初始化：全局变量max_sum设为INT_MIN，确保首次更新时任何正数均有效；
○ 若节点为空，返回0；
○ 递归计算左右子树的最大贡献值left、right，若为负则置为0（舍弃）；
○ 计算当前节点作为路径转折点时的路径和：node->val + left + right；
○ 更新全局最大路径和max_sum；
○ 返回当前节点的最大贡献值：node->val + max(left, right)（仅保留单侧最大贡献）。
3. 主函数调用：通过dfs(root)启动递归，最终返回max_sum作为结果。
四、代码与注释
class Solution {
public:
int maxPathSum(TreeNode* root) {
max_sum = INT_MIN; // 初始化为最小整数值
dfs(root);
return max_sum;
}
private:
int max_sum;
// 后序遍历计算最大路径和
int dfs(TreeNode* node) {
if (!node) return 0;
// 递归计算左右子树的最大贡献值（负数则舍弃）
int left = max(dfs(node->left), 0);
int right = max(dfs(node->right), 0);
// 当前节点作为路径转折点时的路径和
int current_sum = node->val + left + right;
max_sum = max(max_sum, current_sum);
// 返回当前节点的最大贡献值（只能选择左右子树中的一个）
return node->val + max(left, right);
}
};五、总结
本解法通过动态规划与后序遍历的结合，巧妙解决二叉树最大路径和问题。关键在于“自底向上”计算节点贡献，并灵活处理负数情况避免路径恶化。时间复杂度O(n)（遍历所有节点），空间复杂度O(n)（递归栈空间）。适用于需要求解树中任意路径最值的场景，体现了算法设计与问题转化的精髓。
原创内容 转载请注明出处
