即使在遞歸返回後，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仍然保留值

回答

相關問題