I am not sure where I did wrong. Need help!


  • 0
    G
        /**
         * Definition for binary tree
         * public class TreeNode {
         *     int val;
         *     TreeNode left;
         *     TreeNode right;
         *     TreeNode(int x) { val = x; }
         * }
         */
     public class Solution {
        
            private static int maximum = Integer.MIN_VALUE;
            public static int maxPathSum(TreeNode root) {
                maximum = Integer.MIN_VALUE;//the function would call many times, so need to reset maximum every time it called
                maxPath(root);
                return maximum;
            }
            private static int maxPath(TreeNode root) {
                if(root == null)
                    return Integer.MIN_VALUE;
                if( root.left== null && root.right == null){
                     if(root.val > maximum)
                        maximum = root.val;
                     return root.val;
                
                }
                   
                int leftPath =  maxPath(root.left);
                int rightPath = maxPath(root.right);
                int sum = leftPath + rightPath + root.val;
                int maxNum = findMax( root.val, leftPath+ root.val, rightPath+ root.val);
                if ( Math.max(sum, maxNum) > maximum)
                    maximum = Math.max(sum, maxNum) ;
                return maxNum;
                
            }
            
            private static int findMax ( int a, int b, int c){
                int tmp1 = Math.max(a,b);
                
                return Math.max(tmp1,c);
            }
        }
    

    I got wrong with { -2 1 } input the expected should be 1, but mine returns 21445223 ( can't remember the exact number but it is pretty large). I guess I need to reset my global variable every time call maxPathSum, but still doesn't work.


  • 0
    D

    The problem is negative number overflow.

    int leftPath =  maxPath(root.left);
    int rightPath = maxPath(root.right);
    int sum = leftPath + rightPath + root.val;
    

    for the [-2, 1] case, leftPath is 1 and rightPath is Integer.MIN_VALUE. Thus:
    sum = 1 + Integer.MIN_VALUE -2, which is Integer.MIN_VALUE - 1, overflow (or underflow?)

    change:

    if(root == null)
        return Integer.MIN_VALUE;
    

    to:

    if(root == null)
        return 0;
    

    it will pass


Log in to reply
 

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