LeetCode 124. Binary Tree Maximum Path Sum

LeetCode 124. Binary Tree Maximum Path Sum

LINK: https://leetcode.com/problems/binary-tree-maximum-path-sum/

Matter

You are given the root of a binary tree.

Find the maximum possible sum of values along any path in the tree.
A path can start and end at any node, but each node can only be used once.

Example.

[1]
Input:
root = [1,2,3]

Output:
6

Explanation:
The best path is 2 -> 1 -> 3, which sums to 6.

[2]
Input:
root = [-10,9,20,null,null,15,7]

Output:
42

Explanation:
The best path is 15 -> 20 -> 7, which sums to 42.

Constraints

1 <= number of nodes <= $3 \times 10^4$

-$1000$ <= Node.val <= $1000$

Problem analysis

This problem is similar to the diameter problem, but instead of counting edges, we sum node values.

At each node, we consider:

• the best path coming from the left
• the best path coming from the right

However, negative paths should be ignored because they reduce the total sum.

So we take:

left = max(0, left_subtree_sum)
right = max(0, right_subtree_sum)

Solution

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 maxSum = std::numeric_limits<int>::min();
        maxPathDown(root, maxSum);
        return maxSum;  
    }
private:
    int maxPathDown(TreeNode* node, int& maxSum) 
    {
        if (!node) 
            return 0;
        
        // Prevent from minus path, If sum is minus, never include.
        int leftMax = std::max(maxPathDown(node->left, maxSum), 0);
        int rightMax = std::max(maxPathDown(node->right, maxSum), 0);
        maxSum = std::max(maxSum, leftMax + rightMax + node->val);
        
        // Return the maximum path sum going down from the current node
        return std::max(leftMax, rightMax) + node->val;
    }
};