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


  • 2
    J

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

  • 0
    Z

    also stuck here... confused by the case


  • 4
    A

    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).


Log in to reply
 

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