牛客125题解：二叉树最大路径和的动态规划解法

一、题目解读

牛客125题要求求解一棵二叉树中节点之间的最大路径和。路径定义为任意两个节点之间的连通路径（无需经过根节点），节点值可正可负。核心在于找到包含节点值之和最大的路径，需考虑子树贡献与全局最优解的权衡。

二、解题思路

1. 后序遍历：通过递归遍历二叉树，自底向上计算每个节点的贡献；

2. 动态规划：维护两个值：

○ 当前节点为路径起点的最大路径和（需包含左右子树中较大的贡献）；

○ 全局最大路径和（更新所有可能路径中的最大值）；

3. 处理负数：若子树贡献为负，则舍弃该子树，避免影响整体路径和。

三、解题步骤

1. 初始化：全局变量max_sum设为INT_MIN，确保首次更新时任何正数均有效；

2. 递归函数DFS：

○ 若节点为空，返回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)（递归栈空间）。适用于需要求解树中任意路径最值的场景，体现了算法设计与问题转化的精髓。