Short Java solution. Recursion.


  • 118
    P

    I use recursive solution to solve the problem.

    public int sumNumbers(TreeNode root) {
    	return sum(root, 0);
    }
    
    public int sum(TreeNode n, int s){
    	if (n == null) return 0;
    	if (n.right == null && n.left == null) return s*10 + n.val;
    	return sum(n.left, s*10 + n.val) + sum(n.right, s*10 + n.val);
    }

  • 0
    T
    This post is deleted!

  • 1
    T

    Shouldn't we consider integer overflow?


  • 1
    P

    The return type provided by problem creator is 'int'. So I think we shouldn't consider overflow.


  • 0
    T

    What if one of paths forms "4294967295" which is larger than Integer.MAX_VALUE and will be regarded as -1 because it is complement of "-1" in int datatype. In this case, should we return Integer.MAX_VALUE?


  • 0
    T
    This post is deleted!

  • 0
    R

    Very nice solution! Can't help myself but to try this out in one line :

     public int sum(TreeNode n, int s) {
            return (n == null) ? 0 :
                    ((n.right == null && n.left == null) ? s * 10 + n.val :
                            sum(n.left, s * 10 + n.val) + sum(n.right, s * 10 + n.val));
        }
    

  • 0
    G

    Excellent code! (y)


  • 7
    L
        public int sumNumbers(TreeNode root) {
            return helper(root, 0);
        }
        
        public int helper(TreeNode root, int curSum) {
            if(root == null) return 0;
            curSum = curSum*10 + root.val;
            if(root.left == null && root.right == null) return curSum;
            return helper(root.left, curSum) + helper(root.right, curSum);
        }
    }
    

    Same idea, what is the running time? recent days time cost of java code is really crazy...... I don't know if there is something wrong with OJ.


  • 0
    I

    I believe this is because OJ starts calculating before JVM is up. Usually turning on the JVM takes some times but when we turn it on we don't need to turn it off.


  • 0
    Z

    brilliant! and very beautiful


  • 0
    Z

    it is really perfect


  • 2
        public int sumNumbers(TreeNode root) {
          return helper(root, 0);  
        }
        
        int helper(TreeNode node, int sum){
          if(node == null) return 0;
          sum = sum * 10 + node.val;
          if(node.left == null && node.right == null) return sum;
          return helper(node.left, sum) + helper(node.right, sum);
        }

  • 0

    Beautiful approach !


  • 0
    T

    clean and concise!!!!


  • 0
    N

    Thanks for the solution, introduced variables to further improve readability,

      public int sumNumbers(TreeNode root) {
        return sumNodes(root, 0);
      }
    
      private int sumNodes(TreeNode root, int currentSum) {
        if (root == null) return 0;
        currentSum = currentSum * 10 + root.val;
        if (root.left == null && root.right == null) return currentSum;
        int leftSum = sumNodes(root.left, currentSum);
        int rightSum = sumNodes(root.right, currentSum);
        return leftSum + rightSum;
      }
    

  • 0
    J

    I have the same recursion idea, but I make my helper function void type. It turned out that my code can't pass the case[0,1] when I submitted. However, when I used "Run code" with the case, it got the correct result. CONFUSING......

    Can anyone find out the problem?

    """
    public static int res = 0;

    public int sumNumbers(TreeNode root) {
        dfs(root, 0);
        return res;
    }
    
    public void dfs(TreeNode root,int cur){
    	if(root == null) return;
    	
    	if(root.left == null && root.right == null){
    		res += cur * 10 + root.val;
    		return;
    	}
    	
    	
    	dfs(root.left, cur * 10 + root.val);
    	dfs(root.right, cur * 10 + root.val);
    }
    

    """


Log in to reply
 

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