递归过程中的奇怪bug

sd2nnvve  于 2021-07-06  发布在  Java
关注(0)|答案(1)|浏览(367)

下面的代码构建了一个二叉树,其中所有节点都是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]
...

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

klsxnrf1

klsxnrf11#

我无法运行你发布的代码,因为它不完整。下一次发布一个sscce和一些特定的测试数据来显示“奇怪”的行为可能是个好主意。
但从我所看到的情况来看,我猜问题出在你通过考试的方式上 LinkedList<Integer> path 中的参数 printPathsRecur 方法。
您正在中创建路径链表 printPaths() 方法。然后将引用传递给 printPathsRecur() 方法。它修改列表,然后递归地自身运行两次,将相同的引用传递给您在 printPaths() 方法。意味着在任何时候 printPathsRecur() 方法实际上正在处理它一直添加到的同一个列表,在所有2d链表中创建一个长列表。只是对同一个链表的许多引用。

相关问题