即使在递归返回后，LinkedList仍然保留值

我有这个函数来查找BST中从根到叶的所有路径。即使在递归返回后，LinkedList仍然保留值

public static void paths(Node node, LinkedList<Integer> list) { 

    if (node == null) { 
     return; 
    } 
    list.add(node.data); 

    if (node.left == null && node.right == null) { 
     print(list); 
     return; 
    } else { 
     paths(node.left, list); 
     paths(node.right, list); 
    } 
} 

public static void print(LinkedList<Integer> list1) { 
    System.out.println("Contents of list: " + list1); 
}

我把它用：

LinkedList list = new LinkedList(); 
paths(bt.root, list);

如：

07 
02 
01 05

它打印：

7 2 1 
7 2 1 5 [instead of 7 2 5]

不知何故，值1被保存在 “名单”，甚至从递归返回后。

来源

2012-01-30 mihirk

正如其他人所说，这里只有一个LinkedList对象在使用。 xyz错误地将此描述为使用按引用传递，但它实际上传递的值为list，其中是的引用值。（改变参数本身，例如为它指定一个不同的值，都没有给调用者可见;在对象中改变的参数指是可见的。）

这真的重要的，你明白变量，对象和引用如何在Java中工作。当你写（说）：

Node node = new Node();

...那么node值不是一个Node对象。这是一个参考到Node对象。赋值和参数传递处理该值（引用）而不是对象。因此，例如：

Node node1 = new Node(); 
Node node2 = node1;

node1和node2现在指的是同一个对象 - 有没有涉及对象拷贝。

至于你如何解决这个问题，有映入脑海两个选项：

每个递归步骤创建链表的副本，这样的变化是独立
“弹出“方法结尾的链表末尾的新增值，这样当递归深度方法完成时，链表将回到具有n-1元素。
```
list.removeLast(); 
```
无论是在两个分支，或者在finally块，或取出明确return：

您可以通过简单地添加到呼叫做到这一点

if (node.left == null && node.right == null) { 
    print(list); 
    // Note no return statement 
} else { 
    paths(node.left, list); 
    paths(node.right, list); 
} 
list.removeLast();

来源

2012-01-30 07:21:13

谢谢你的回复。它真的帮我清楚了我的Java通过价值观的概念！ – mihirk 2012-01-30 07:33:12

我没有看到你从列表中删除任何东西。所以它一旦添加就停留在那里。

来源

2012-01-30 06:44:06 Bozho

我称之为“路径（node.left，list）“递归。所以当它返回时，我预计它只有7和2。为什么它仍然包含1？ – mihirk 2012-01-30 06:46:28

列表通过refference传递，因此任何一个递归分支中的任何更改都可以在任何地方看到 – xyz 2012-01-30 06:48:54

认真吗？为什么列表通过引用传递？因为当我使用数组而不是列表时，它工作正常。所以数组是按值传递的！但那么通过引用传递什么以及通过价值传递了什么呢？我怎么记得。 – mihirk 2012-01-30 06:52:27

该列表在递归函数的范围之外创建，这意味着它与在所有递归调用中使用的列表相同。您正在向列表递归添加元素，因此即使在一个递归序列中值为7 2 5，1也会被添加到另一个递归序列中的相同列表中。

来源

2012-01-30 06:50:08 Dawood

所以调用LinkedList list = new LinkedList（）;路径（bt.root，list）;是不正确的！你能建议必要的改变吗？ – mihirk 2012-01-30 06:55:49

即使在递归返回后，LinkedList仍然保留值

回答

相关问题