# Wrong answer for Input: {1,-2,-3,1,3,-2,#,-1} Output: 4 Expected: 3

• I got wrong answer for my code.
Input: {1,-2,-3,1,3,-2,#,-1}
Output: 4
Expected: 3

If a path is from any node to any node, then node 1 and node 3 should give the biggest sum.
I used a stack to implement dfs

``````class Solution {
public:
int maxPathSum(TreeNode *root) {
if(root == NULL) return -INT_MAX;
stack<TreeNode*> s;
int max_to_here = 0;
int cur_max = -INT_MAX;
s.push(root);
while(!s.empty())
{
TreeNode *node = s.top();
s.pop();
if(node!=NULL)
{
int temp_max = max_to_here + node->val;
max_to_here = std::max(temp_max, node->val);
if(max_to_here > cur_max)
{
cur_max = max_to_here;
}
s.push(node->left);
s.push(node->right);
}
}
return cur_max;
}
};``````

• also stuck here... confused by the case

• The tree looks like:

``````                      1
/       \
-2        -3
/   \      /
1     3   -2
/
-1
``````

The problem is asking: the max sum of a path which connects (arbitrary) two 'connected' nodes (i.e., root + node + leaf) in the tree. I guess it also includes the the case: starting from a node, and ending at the same node.
So, in above case, the answer should be 3 (the leaf node).

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