打印所有路径总和的算法

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

应该return:

路径 1: 4 + 5 + 7

路径 2: 4 + 5 + 8 + 9

路径 3: 4 + 6 + 10

所以路径总和应该是：path1 + path2 + path3

如何使用

解决问题

递归
非递归

我找到了非递归的解决方案，但对递归方法有一些小问题

非递归方法：

/**
 * 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);
}

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

获得答案的一种方法是迭代 List> 并获得答案，但我认为它效率低下。我们如何仅在 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);
}

打印所有路径总和的算法

Algorithm to print the total sum of all the path

algorithm

recursion

binary-tree

non-recursive