java - 给定一棵二叉树和一个总和，找到所有根到叶路径，其中每个路径的总和等于给定的总和

Question

为什么最后使用“path.remove(path.size()-1)”？

此代码用于查找总和等于给定总和的所有根到叶路径。

public List<List<Integer>> pathSum(TreeNode root, int sum) {
    List<List<Integer>> res = new ArrayList<List<Integer>>();
    ArrayList<Integer> path = new ArrayList<Integer>();
    pathSumRe(root, sum, res, path);
    return res;
}
public void pathSumRe(TreeNode root, int sum, List<List<Integer>> res,
        ArrayList<Integer> path) {

    if (root == null)
        return;

    path.add(root.val);

    if (root.left == null && root.right == null && root.val == sum) {

        ArrayList<Integer> tmp = new ArrayList<Integer>(path);
        res.add(tmp);
    }

    pathSumRe(root.left, sum - root.val, res, path);
    pathSumRe(root.right, sum - root.val, res, path);
    path.remove(path.size() - 1);
}

删除“path.remove(path.size() - 1);”代码将给出以下输出。

输入:[0,1,1], 1

输出:[[0,1],[0,1,1]] ==>这是错误的输出

预期输出:[[0,1],[0,1]]

Answer 1

path.remove(path.size() - 1) 正在从 path 列表中删除最后添加的节点，因为您对所有节点重复使用相同的列表递归迭代，并在每个方法执行中使用 path.add(root.val); 添加当前节点。

<小时/>

以下内容是等效的，无需重复使用相同的列表(并为每次执行创建一个新列表):

public void pathSumRe(TreeNode root, int sum, List<List<Integer>> res,
        ArrayList<Integer> path) {
    if (root == null) {
        return;
    }
    path.add(root.val);
    if (root.left == null && root.right == null && root.val == sum) {
        res.add(new ArrayList<Integer>(path));
    }
    pathSumRe(root.left, sum - root.val, res, new ArrayList<Integer>(path));
    pathSumRe(root.right, sum - root.val, res, new ArrayList<Integer>(path));
}

这更容易理解，但会创建更多新的 ArrayList(取决于树结构)。无论您进行何种编辑，两个版本都可以正确地用于如下所示的 TreeNode:

class TreeNode {
    public final int val;
    public final TreeNode left;
    public final TreeNode right;

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