打印所有路径的总和的算法

Question

给你一个二叉树，定义如下：

public class TreeNode {
    public int val;
    public TreeNode left, right;
    public TreeNode(int val) {
        this.val = val;
        this.left = this.right = null;
    }
}

打印所有路径的总和，路径定义为从根节点到任意叶节点的线

例如：

4 5 6 7 8 10 # # # # 9

应返回：

路径 1： 4 + 5 + 7

路径 2： 4 + 5 + 8 + 9

路径3： 4 + 6 + 10

所以总路径

总和应该是：路径 1 + 路径 2 + 路径 3

我们如何通过使用来解决问题

• 递归的
• 非递归

我已经通过使用非递归找到了解决方案，但是对递归方法有一些小问题

非递归方法：

/**
 * non-recursive
 */
public static int pathSum2(TreeNode root) {
    int sum = 0;
    if (root == null) {
        return sum;
    }
    Queue<TreeNode> queueNode = new LinkedList<TreeNode>();
    Queue<Integer> queueSum = new LinkedList<Integer>();
    queueNode.add(root);
    queueSum.add(root.val);
    while (!queueNode.isEmpty()) {
        TreeNode node = queueNode.poll();
        int temp = queueSum.poll();
        if (node.left == null && node.right == null) {
            sum += temp;
        }
        if (node.left != null) {
            queueNode.add(node.left);
            queueSum.add(node.left.val + temp);
        }
        if (node.right != null) {
            queueNode.add(node.right);
            queueSum.add(node.right.val + temp);
        }
    }
    return sum;
}

递归方法：

/**
 * recursive
 */
public List<List<Integer>> pathSum(TreeNode root) {
    List<List<Integer>> rst = new ArrayList<List<Integer>>();
    helper(rst, new ArrayList<Integer>(), root);
    return rst;
}
public void helper(List<List<Integer>> rst, ArrayList<Integer> list,
                   TreeNode root) {
    if (root == null) {
        return;
    }
    list.add(root.val);
    if (root.left == null && root.right == null) {
        rst.add(new ArrayList<Integer>(list));
    }
    helper(rst, list, root.left);
    helper(rst, list, root.right);
    list.remove(list.size() - 1);
}

但是这样，我输出的是所有路径，如果我想获得这些路径的总和怎么办？

获得答案的一种方法是迭代列表>并得到答案，但我认为它效率低下。我们如何在helper()方法中处理这个问题，因为对于总和来说，java只是pass-by-value

Answer 1

我通过使用递归找到了解决方案

/**
 * recursive
 */
public List<List<Integer>> pathSum(TreeNode root, int sum) {
    List<List<Integer>> rst = new ArrayList<List<Integer>>();
    helper(rst, new ArrayList<Integer>(), root, sum);
    return rst;
}
public void helper(List<List<Integer>> rst, ArrayList<Integer> list,
                   TreeNode root, int sum) {
    if (root == null) {
        return;
    }
    list.add(root.val);
    if (root.left == null && root.right == null) {
        rst.add(new ArrayList<Integer>(list));
    }
    helper(rst, list, root.left, sum - root.val);
    helper(rst, list, root.right, sum - root.val);
    list.remove(list.size() - 1);
}