树：根到叶之和（递归）

Question

问题是：计算所有根到叶数的总和。例如：如果树是（1,2,3），1是根，2是左子，3是右子，两条路径：1-

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

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;
}

但是当我在helper方法中添加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的值没有“转移”回getSum方法中的sum。

Answer 1

ZouZou关于传递值的看法是正确的，尽管这只适用于原语。将求和改为整数而不是int应该可以做到这一点，另一个解决方案是给我们一个全局变量（即字段）

Answer 2

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();
    }
}