Run time Error ! Can someone point me the mistakes in my code ?


  • 1
    Y
        public class Solution {
    public int sumNumbers(TreeNode root) {
        int result =0;
        // create two empty string to represent the left and right tree value(if exist) separately
        String sleft = ""; 
        String sright = "";
       // not empty tree add append root to both string
       if(root!=null){
           sleft += root.val;
           sright+= root.val;
         // left subtree is not empty, append the left value to the left string and recursive call the left subtree
           if(root.left!=null){
               sleft += root.left.val;
               sleft += sumNumbers(root.left);
           }
     // right subtree is not empty, append the right value to the right string and recursive call the right subtree
           if(root.right!=null){
               sright += root.right.val;
               sright += sumNumbers(root.right);
           }
     // reverse the two string and get the correct answer;
           String sleftreverse = reverse(sleft);
           String srightreverse = reverse(sright);
           result = Integer.parseInt(sleftreverse)+Integer.parseInt(srightreverse);
       }
     return result;
    }
    
    private static String reverse(String s){
           String result = "";
           for(int i=s.length()-1;i>=0;i--){
               result += s.charAt(i);
           }
           return result;
       }   
    }

  • 1
    M

    The technical cause of your runtime error is that parseInt() is trying to convert a string, but the result is too large to store in an int, therefore it throws a NumberFormatException. In the documentation, the pertinent example follows:
    [parseInt("2147483648", 10) throws a NumberFormatException][1]

    I'm also not sure what you are trying in the algorithm, but it looks like you append each value to the string, then try to parse it. Addition in strings does not work in the way you've coded. What is currently happening looks like this:

    Imagine a tree like the following:

       50
    15    22
             103
    

    The right hand subtree would have this order of execution.

    Node 50 ->
      50.sright = "50"       (sright += root.val)
      50.sright = "5022"   (sright += root.right.val)
      sumNumbers(50.right)
        Node 22 ->
          22.sleft = "22" (sleft += root.val)
          22.sright = "22" (sright+=root.val)
          22.sright = "22103" (sright+=root.right.val)
          sumNumbers(22.right)
            Node 103 ->
              103.sleft = "103" (sleft += root.val)
              103.sright = "103" (sright += root.val)
              103.slr = "301" (slr = reverse(sleft))
              103.srr = "301" (srr = reverse(sright))
              return parse(slr)+parse(srr) = 301+301 = 602
          22.sright = "22103602" (sright+=sumNumbers(22.right))
          22.slr = "22" (slr = reverse(sleft))
          22.srr = "20630122" (srr = reverse(sright))
          return parse(slr)+parse(srr) = 22+20630122 = 20630144
      50.sright = "5020630144" (sright += sumNumbers(50.right))
      50.srr = "4410360250" (srr = reverse(sright))
      parse(srr) = 4410360250 -> NumberFormatException (num > 2147483647, cannot fit in int)
    

    This is what I assume you are attempting (has been accepted):

        public int sumNumbers(TreeNode root) {
            if(root==null) return 0;
            return sums(root,"0");
        }
        public int sums(TreeNode root,String sum){
            sum = sum+root.val;
            int lval = 0;
            int rval = 0;
            if(root.left != null) lval = sums(root.left,sum);
            if(root.right != null) rval = sums(root.right,sum);
            if(root.left == null && root.right==null){
                return Integer.parseInt(sum);
            }
            else{
                return lval+rval;
            }
        }
    }
    

    The main problem with this one is if the tree is too large, in which case we get an integer overflow error.
    [1]: http://docs.oracle.com/javase/7/docs/api/java/lang/Integer.html#parseInt(java.lang.String, int)


  • 0
    Y

    Thx for pointing it out. I am wondering what is the correct way to solve the problem without worrying about overflow? Also, why are you declaring the method sums as a instance method instead of using static keyword? what's the difference between them?


  • 0
    M

    Overflow in this case would mean the answer could not fit in an int. In that case, you would need to change the method declaration and return type. In other words, it isn't safe, but the only thing we could do to fix it is return an error.

    The difference between static and non-static methods is how you call them and what access they have to instance variables. As Solution is a class instantiated in a outside class, non-static methods are those that can by called using Solution sol=new Solution();sol.sumNumbers(root);

    They have access to instance variables, which are the ones specific to sol, rather than to Solution. Static methods are tied to Solution, and so cannot access any variable or method specific to any instance. Trying gives an error.

    Calling a static method from a non-static context when there are no instance variables doesn't really have any effect, but I prefer staying in the same context when I can.


Log in to reply
 

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