The solution is not straightforward but once you see the code, it is really intuitive. See below:
class Solution {
public:
int maxSum = INT_MIN;
int maxPathSum(TreeNode* root) {
if (!root)
return 0;
helper(root);
return maxSum;
}
int helper (TreeNode* root) {
if (root == NULL)
return 0;
int left = max(0, helper(root->left));
int right = max(0, helper(root->right));
maxSum = max(left+right+root->val, maxSum);
return root->val + max(left, right);
}
};
The idea is to perform a simple DFS through the tree and get the maximum sum in the left subtree (starting from the left node) and right subtree (starting from the right node) of a node. Now, when the left sum comes out to be negative, it’s better not to include the left subtree path as it will only decrease the total sum. Same greedy approach is applied to the right subtree.
A question which may arise is, what happens when all the nodes in the tree are negative? For example, consider the tree below.
-2
/ \
-1 -4
Answer: -1
Note that in the recursive function helper, we consider the maximum sum for a node to be left+right+root->val. This means that when we process node -2, we will have maxSum=0+0+(-2). When we process node -1, we will have maxSum=0+0+(-1). So we are essentially including negative nodes as well in the answer.