# C++ DFS solution with some explanation.

• The idea is also DFS. From bottom to up, at every node, we have four choices:

1. the left sub-path ==> node ==> the right sub-path

2. the left sub-path ==> node ==> upper. The left sub-path may yield a negative sum, in which case we set node->left sub-path to zero.

3. the right sub-path ==> node ==>upper. The right sub-path may yield a negative sum, in which case we set node->right sub-path to zero.

4. 0 ==> upper, which means we abandon the entire tree rooted at this node because of a negative sum.

Noted: Negative node values are possible.

class Solution
{
private:
int maxPathSum(TreeNode *root, int &ma)
{
if (!root)
return 0;
int left =  maxPathSum(root->left, ma);
int right = maxPathSum(root->right, ma);
ma = max(ma, root->val + left + right);
return max(max(0, max(left, right)) + root->val, 0);
}

public:
int maxPathSum(TreeNode* root)
{
if (!root)
return INT_MIN;  //This INT_MIN is just to comply with the judge.

int ma = root->val;

maxPathSum(root, ma);

return ma;
}

};

• Can you please tell me your thought process in the last two statements of the recursion function, I got stuck at the 70th test case and couldn't wrap my head around the problem until i saw a few solutions.

• @sujiths52 No shortcuts but practice practice practice.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.