This problem comes from leetcode which can be found here. I was reading a solution to this problem which is below

/**
 * 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;
    }
};

I almost understand the logic of this problem but I do not quite understand why we have 0 in the max for the search part in the left and right subtrees. Can someone explain that to me?

CodePudding user response：

The expression l r root->val considers what would be the optimal path for which the highest participating node is the current node.

Consider that it could be possible that this optimal path would not include nodes from the left subtree. In that case we want to make sure that l is 0. That is what this max(0, dfs(root->left, res)) expression accomplishes.

More concretely, if the optimal upward-path that ends in the node's left child turns out to be negative, then it is not optimal to extend that path further upwards with the current node's value. So then 0 is used instead, which practically means we don't use any value from the left subtree.

Obviously the reasoning for establishing the value for r is analogous.