LinkedList即使在从递归返回后也会保留值

我有这个函数来查找BST.中从根到叶的所有路径

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保留在"列表"中，即使它从递归中返回。

正如其他人所说，这里只有一个LinkedList对象在使用。xyz错误地将其描述为使用逐引用传递，但它实际上是逐值传递list的值，是的引用。（参数本身的更改，例如为其分配不同的值，对调用者来说是不可见的；参数所指对象内的更改是可见的。）

了解变量、对象和引用在Java中的工作方式非常重要。当你写（说）：

Node node = new Node();

则CCD_ 3的值不是CCD_。它是对Node对象的引用。赋值和参数传递处理的是该值（引用），而不是对象。例如：

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

node1和node2现在引用同一个对象——不涉及对象复制。

至于如何解决这个问题，脑海中浮现出两个选项：

在每个递归步骤上创建链接列表的副本，以便更改是独立的
将新添加的值从方法末尾的链表末尾"弹出"，这样，当递归深度为n的方法完成时，链表将返回到具有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();

我没有看到您从列表中删除任何内容。所以一旦添加，它就会保持不变。

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

相关内容

最新更新

热门标签：