牛客网125题 二叉树最大路径和：利用递归解决二叉树最优路径

一、问题本质解析

这道题要求我们在二叉树中寻找一条路径，使得路径上节点值的和最大。这里的路径定义非常灵活：

• 可以从任意节点出发

• 可以向上或向下延伸

• 每个节点只能访问一次

二、核心算法思路

1. ‌后序遍历框架‌：采用深度优先搜索的后序遍历方式（左右根）

2. ‌贡献值计算‌：对每个节点计算其左右子树的最大贡献值

3. ‌全局最大值更新‌：在遍历过程中维护全局最大路径和

三、完整代码

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @return int整型
     */
    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);
    }
};

四、关键代码解析

int dfs(TreeNode* node) {    if (!node) return 0;    
    // 计算左右子树贡献值（负数则舍弃）
    int left = max(dfs(node->left), 0);    int right = max(dfs(node->right), 0);    
    // 更新全局最大值
    max_sum = max(max_sum, node->val + left + right);    
    // 返回当前节点的最大贡献值
    return node->val + max(left, right);
}

五、常见误区提醒

1. 忘记处理负数节点的情况

2. 混淆路径方向（以为只能从上往下）

3. 没有正确理解"每个节点只能出现一次"的限制

六、扩展思考

1. 如果要求输出具体路径而不仅是和，该如何修改算法？

2. 如果路径定义改为必须从叶子到叶子，算法该如何调整？

3. 在超大规模树结构下，如何优化内存使用？

通过这个案例，我们学习了如何利用递归和全局变量来高效解决树形结构中的最优路径问题，这种思想在算法设计中非常重要。