首页 文章

tree：root到leaf sum（递归）

提问于
浏览 次
0

问题是：计算所有根对叶数的总和 . 例如：如果树是（1,2,3），1是根，2是左子，3是右子，两条路径：1-> 2 1-> 3，sum = 12 13 = 25

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

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 的值不是'transferred'回到 sum 在 getSum 方法中 .

java recursion tree

2 回答

  • 1
    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();
    }
}
    回复于
  • 0

    ZouZou对于值的传递是正确的，尽管这仅适用于原语 . 将您的总和更改为Integer而不是int应该可以解决问题，其他解决方案将是我们一个全局变量（即字段）

    回复于

相关问题