I got wrong result {1} for the input {-3} in oj. Can't find the where is the mistake.


  • 0
    S

    int max;

    public int maxPathSum(TreeNode root){

          max = Integer.MIN_VALUE;	
          helper(root);
          return max;
    		
    	}
        
    	
    	public int helper(TreeNode root){
    		if(root == null)
    			return 0;
    		
    		int left = helper(root.left);
    		int right = helper(root.right);
    		
    		
    		int result = Math.max(root.val, Math.max(root.val + left, root.val + right));
    		
    		max = Math.max(root.val + left + right, Math.max(max, result));
    		
    		return result;
    }

  • 0
    F

    there are several bugs in the code:

    1. Don't use static, I guess the OJ is running test case parallel, so if you using static, it will mess the result. for the case {-3}, your code won't return 1 if running in single thread, but it could be anything since it is static when run test cases in parallel.

    2. help method should not directly return max. if you just try to had a previous max for left tree, and right tree's result is less than left tree, return max will put the left tree's result to right tree. it should return result.

    3. should change
      {
      int result = Math.max(Math.max(root.val, Math.max(root.val + left, root.val + right)), left + right + root.val);
      max = (Math.max(max, result));
      }

    to:
    {
    int result = Math.max(root.val, Math.max(root.val + left, root.val + right));
    max = Math.max((Math.max(max, result)), left + right + root.val);
    }

    when calculate the sub tree max, it should include left+right+self. since we only can choose one path when it's parent calculate the result.


  • 0
    S

    Hi @Sining, just update your code format. Hope you can enhance your post with some words to explain your idea.


  • 0
    S

    get passed now. Already updated the code. Thank you @frankgdchen.

    1.left = left sub tree's max sum
    2.right = right sub tree's max sum
    3.result = the max path sum with the path go through root but not ending at root
    4.max = max sum so far.


Log in to reply
 

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