递归过程中的奇怪错误

Question

我有以下代码，它构建了一个二进制树，其中所有节点都是0或1，因此从根到叶的每条路径都是一个特定长度的二进制字符串。最初，我的代码只是打印所有路径(路径是一个整数列表，即[0，0，0，1，0，1](。现在我正试图将所有路径保存在列表中，但我得到了意外的输出。以下是相关代码：

public class Tree{
Node root;
int levels;
LinkedList<LinkedList<Integer>> all;
Tree(int v){
root = new Node(v);
levels = 1;
all = new LinkedList<LinkedList<Integer>>();
}
public static void main(String[] args){
Tree tree = new Tree(0);
populate(tree, tree.root, tree.levels);
tree.printPaths(tree.root);  // this is the part that prints the paths one by one
for (LinkedList<Integer> l: tree.all){ // this is when i later tried to save all paths to the
System.out.println(l);               // list all and then print them out from that list
}
}

public void printPaths(Node node)
{
LinkedList<Integer> path = new LinkedList<Integer>();
printPathsRecur(node, path, 0);
}
void printPathsRecur(Node node, LinkedList<Integer> path, int pathLen)
{
if (node == null)
return;
// append this node to the path array
path.add(node.value);
path.set(pathLen, node.value);
pathLen++;
// it's a leaf, so print the path that led to here
if (node.left == null && node.right == null){
printArray(path, pathLen); // Initial version which prints the paths one by one - WORKS FINE
all.add(path);  // This is when I try to actually keep the paths in a list - doesn't work
}
else
{
printPathsRecur(node.left, path, pathLen);
printPathsRecur(node.right, path, pathLen);
}
}
...}

本质上，当我只是一个接一个地打印它们而不保存它们时，我得到了预期的输出：

...
0 1 0 0 1 0
0 1 0 0 1 1
0 1 0 1 0 0
0 1 0 1 0 1
...

但是，当我试图将路径保存到列表列表中，并打印该列表的每个元素时，我会得到以下信息：

[0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1]
[0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1]
...

看起来列表只是一次又一次地保存相同的超长条目。

Answer 1

我无法运行您发布的代码，因为它不完整。张贴SSCCE和一些显示"；怪异的"；下次的行为。

但从我所看到的情况来看，我想问题在于您在printPathsRecur方法中传递LinkedList<Integer> path参数的方式。

您正在printPaths()方法中创建路径链接列表。然后将对它的引用传递给printPathsRecur()方法。它修改列表，然后递归地运行自己两次，将相同的引用传递给您在printPaths()方法中创建的原始路径链表。这意味着在任何时候，printPathsRecur()方法的所有递归调用实际上都在使用它不断添加到的同一列表，在all2D链表中创建一个长列表。只是对同一个链表的许多引用。