LeetCode 113路径总和II：为何不能直接将List<Integer>加入List<List<Integer>>

我在解决LeetCode 113 Path Sum II问题时，使用了以下代码实现：

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        dfs(root, targetSum, new ArrayList<>());
        return res;
    }
    private void dfs (TreeNode node, int targetSum, List<Integer> list) {
        if (node == null) return;
        list.add(node.val);
        if (targetSum == node.val && node.left == null && node.right == null) {
            res.add(new ArrayList<>(list));
        }else {
            if (node.left != null) dfs(node.left, targetSum - node.val, list);
            if (node.right != null) dfs(node.right, targetSum - node.val, list);

        }
        list.remove(list.size() - 1);
    }
}

当我把res.add(new ArrayList<>(list))改成res.add(list)时，得到的结果是[[],[]]，而预期结果应该是[[5,4,11,2],[5,8,4,5]]。

我疑惑为什么不能直接用res.add(list);，毕竟list是通过ArrayList<>()定义的。我知道List是接口，ArrayList是实现类，也了解两种二维列表的定义方式：

• List<List<Integer>> res = new ArrayList<List<Integer>>();
• List<List<Integer>> res = new ArrayList<>();
  但还是搞不懂这个问题。

问题原因解析 #

Java中对象是引用传递，你传入的list是同一个ArrayList对象的引用。执行res.add(list)时，只是把这个引用添加到结果列表res中，并没有复制出一个新的列表。

在DFS的回溯过程中，你会执行list.remove(list.size() - 1)移除当前节点的值，这个操作会直接修改那个被所有引用指向的同一个ArrayList对象。当整个DFS结束后，这个list已经被回溯清空，所以res里保存的所有引用指向的都是同一个空列表，最终结果就是[[],[]]。

而res.add(new ArrayList<>(list))会创建一个新的ArrayList对象，并把当前list的元素复制进去，res里保存的是独立的新列表，后续对原list的回溯修改不会影响到这些已保存的新列表，因此能得到正确结果。

关于二维列表定义方式的补充 #

你提到的两种二维列表定义方式本质等价：

• 第一种是显式指定泛型类型的写法
• 第二种是Java 7及以上支持的菱形语法，编译器会自动推断泛型类型，只是简化了代码书写，两者都可以用来存储ArrayList类型的子列表。

内容的提问来源于stack exchange，提问作者Anna