树：根到叶和（递归）

问题是：计算所有根到叶数的总和。例如：如果树是（1,2,3），1是根，2是左孩子，3是右孩子，两个路径：1-> 2 1-> 3，sum = 12 + 13 = 25树：根到叶和（递归）

这是我正确的递归解决方案。在辅助方法，返回总和：

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

，但是当我加入sum作为辅助方法的参数，我总是得到0

public int getSum(TreeNode root) { 
    int sum = 0, path = 0; 
    helper(root, path, sum); 
    return sum; 
} 
private void helper(TreeNode root, int path, int sum) { 
    if (root == null) { 
     return; 
    } 
    int path = 10 * path + root.val; 
    if (root.left == null && root.right == null) { 
     sum += path; 
     return; 
    } 
    helper(root.left, path, sum); 
    helper(root.right, path, sum); 
}

我相信一定会有一些点我误解了递归。预先感谢你给我一些解释，为什么sum的值不是'转移'回sum的getSum方法。

来源

2014-12-10 Zzz...

Java是按值传递的。当你在'getSum'方法中执行'helper（root，path，sum）'时，它不会更新你传递的sum变量作为参数。 – 2014-12-10 22:27:51

@邹邹谢谢。所以，无论辅助方法发生了什么，getSum中的总和保持不变。但如果可能参数是列表，则值将被更新。 – 2014-12-10 22:39:51

邹邹对传递的价值是正确的，虽然这只适用于原语。把你的总和改为Integer而不是int应该可以做到，其他解决方案对我们来说是一个全局变量（即字段）

来源

2014-12-10 22:40:09 wgitscht

错误这也适用于参考。要理解的技巧是引用是按值传递的。而且，Integer是不可变的。 – 2014-12-10 22:40:47

表示同意，整数是不可变的，自动装箱就是这样做的，它是我的头脑技巧。如果你这样说（参考文献是以价值观的形式传递的），你可能会说它是全部通过价值传递的，尽管可能会感到惊讶，我还听到了逐个对象共享这个术语。不过，第二个建议将起作用。 – wgitscht 2014-12-10 22:56:38

Also you need to think about overflow. My solution has passed in LeetCode, hopefully it gives you some tips. 


public class Solution { 
    private long sum = 0; 
    public int sumNumbers(TreeNode root) { 
     if(root == null) return 0; 
     sum(root, new Stack<Integer>()); 

     if(this.sum >= Integer.MAX_VALUE){ 
      return Integer.MAX_VALUE; 
     } 
     return (int)this.sum; 
    } 

    private void sum(TreeNode node, Stack<Integer> stack){ 
     if(node == null) return; 
     stack.push(node.val); 
     if(node.left == null && node.right == null){ 
      long tempSum = 0; 
      int index = 0; 
      for(int i=stack.size()-1;i>=0;i--){ 
       int k = stack.get(i); 
       int times = (int)Math.pow(10, index++); 
       k *= times; 
       tempSum += k; 
      } 
      this.sum += tempSum; 
     } 

     sum(node.left, stack); 
     sum(node.right, stack); 
     if(stack.size() > 0) 
      stack.pop(); 
    } 
}

来源

2015-03-22 13:10:07

树：根到叶和（递归）

回答

相关问题