二叉树最大路径和问题：为何DFS中取左右子树结果与0的最大值？

这是LeetCode上的二叉树最大路径和问题，我阅读了如下题解代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int maxPathSum(TreeNode* root) {
        int res = INT_MIN;
        dfs(root, res);
        return res;
    }
    
    int dfs(TreeNode* root, int& res)
    {
        if(!root)
            return 0;
        
        auto l = max(0, dfs(root->left, res)), r = max(0, dfs(root->right, res));
        res = max(res, l + r + root->val);
        
        return max(l, r) + root->val;
    }
};

我基本理解问题逻辑，但不太明白为何在DFS搜索左右子树时，要将结果与0取最大值，恳请解释。

核心原因：只保留有正向增益的子树路径 #

我们的目标是找到最大路径和，如果某个子树能提供的最大路径和是负数，那把它加入当前路径只会让总和变小，还不如直接舍弃这个子树，只保留当前节点的值。

具体场景分析 #

举个简单例子：

• 当前节点值为5，左子树的最大路径和是-3。如果直接把左子树的结果加进来，得到的路径和是5 + (-3) = 2，比只取当前节点的5要小。
• 这时候用max(0, -3)得到0，相当于选择不包含左子树，只保留当前节点，这样向上返回给父节点的就是5，不会拖父节点的后腿。

区分两个关键操作 #

1. 更新全局最大路径res：
   计算l + r + root->val时，l和r已经处理过负数（转为0），这相当于自动忽略了负贡献的子树——如果子树是负的，就不加它，只算当前节点或者加上正贡献的子树。
2. DFS返回值的意义：
   DFS返回的是从当前节点向下延伸的最大单路径和（只能选左或右子树中的一条，因为路径要向上传递给父节点，不能同时走左右分叉）。如果子树的路径和是负的，就舍弃它，只返回当前节点的值，确保父节点能拿到最优的路径选择。

内容的提问来源于stack exchange，提问作者Wolfy