樹：根到葉和（遞歸）

問題是：計算所有根到葉數的總和。例如：如果樹是（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

樹：根到葉和（遞歸）

回答

相關問題