Right answer in eclipse, wrong answer here?


  • 2
    X

    Hi, my code can get the right answer on Eclipse, but not here.
    The last test case is {1,2,3}, for which I got 6 in Eclipse and 7 here. What could the problem be?

    My idea is to check each path and find the local max sum, and add the result into the global max sum only when this value is positive. I also book keep the max value among all the elements. At the end, if the global max is non-negative, return it, else return the max value among all elements to take care of the case where all values are negative.

    public class Solution {
    public int maxPathSum(TreeNode root) {
        if(root == null)
            return 0;
        // always guarantee the input node in dfs is not null
        int pre = 0; // local max sum 
        int pathMax = 0; // max sum in the current path
        Wrapper max = new Wrapper(Integer.MIN_VALUE); // max value over all variables
        Wrapper result = new Wrapper(0); // total max sum over all paths
        
        dfs(root, pre, pathMax, max, result);
        if(result.val <= 0)
            return max.val;
        else
            return result.val;
    }
    void dfs(TreeNode root, int pre, int pathMax, Wrapper max, Wrapper result){
        pre = Math.max(pre,0)+root.val;
        pathMax = pre > pathMax? pre: pathMax;
        max.val = root.val > max.val? root.val: max.val;
        
        if(root.left == null && root.right == null){
            result.val = pathMax > 0? result.val+pathMax : result.val;
            return;
        }
        
        if(root.left != null){
            dfs(root.left, pre, pathMax, max, result);
        }
        if(root.right != null){
            dfs(root.right, pre, pathMax, max, result);
        }
    }
    

    I also used a wrapper class to store my answer

    class Wrapper{
    int val;
    Wrapper(){val = 0;}
    Wrapper(int _val){
        val = _val; }
     }

  • 0
    S

    Could you correct the last part of your code, the last } is out of box. Thanks.


  • 0
    S

    First of all, what does the {1,2,3} look like? It should be like this:

      1
     / \
    2   3
    

    Based on it, I read your code, go through the test case {1,2,3} by hand-writing on paper. I think your code will output 7. Since after go to the node 2 the result will be 3, then go to the node 3 the pathMax will be 4 and 'result' would update to 7.


Log in to reply
 

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