爲什麼在遞歸調用之前實例化一個新列表？

public void dfsSearch (TreeNode root, List<String> curr, List<List<String>> res) { 
     curr.add(String.valueOf(root.val)); 
     // a leaf node has been reached 
     if (root.left == null && root.right == null) { 
      res.add(curr); 
      return; 
     } 
     if (root.left != null) { 
      List<String> temp = new ArrayList<>(curr); 
      dfsSearch(root.left, temp, res); 
     } 
     if (root.right != null) { 
      List<String> temp = new ArrayList<>(curr); 
      dfsSearch(root.right, temp, res); 
     } 
    }

上面的代碼是一個使用dfs來查找二叉樹中從根到葉的所有路徑的方法，我的問題是，在遞歸調用上面的兩行中，爲什麼我需要實例化一個新列表並將此臨時列表（temp）傳遞給遞歸調用，爲什麼我不能只使用curr（函數中的參數）？爲什麼在遞歸調用之前實例化一個新列表？

來源

2017-03-29 Haobo_X

爲了明確這個問題，在每次遞歸調用之前，爲什麼需要在這裏使用一個新的列表temp，並且不能使用curr來代替？ –

由於curr正在遞歸修改。想象一下，你沿着二叉樹的左邊走下去（這就是你在DFS中所做的）。你打了一片葉子，因此curr有通向第一片葉子的路徑。然後當你從遞歸棧中彈出時，如果你使用相同的curr，你會向右移動並添加正確的子節點，因此curr不正確地擁有來自先前遞歸調用的葉子，並且現在具有正確的子節點。 –

我認爲值得一提的是List是一個引用類型。這意味着當你將'curr'列表作爲參數傳遞時，它不會爲被調用的新方法創建一個新對象。它與調用方法具有相同的對象，這就是爲什麼你不爲'res'列表創建一個臨時列表，你想在所有遞歸調用中修改相同的列表 –

想象這是您的二叉樹

 1 
    2 3 
    4 5

比方說，你沒有用temp。然後，你會沿着二叉樹的左側進行遞歸，這意味着curr會添加1,2和4.因爲列表是可變的，所以即使從遞歸棧中彈出，它們的值也會保存在遞歸調用中。所以在curr加4之後，你會回到node 2，往右邊加5，這樣curr將包含1,2,4,5而不是你想要的，1,2,4和1,2 5。

來源

2017-03-29 21:38:55

明白了，就像Freddy Hdz所說的，java中的List是一個引用類型，如果我不創建一個新的列表，我將最終使用相同的curr來調用和調用方法，謝謝！ –

這些副本用於防止在dfsSearch方法遞歸調用時同時修改curr。第一行curr.add(String.valueOf(root.val));修改了curr集合，並且在修改集合時無法循環訪問集合。

來源

2017-03-29 21:29:34 rmirabelle

你怎麼知道這個方法被同時調用？ –

遞歸本身是併發的來源。雖然外部/父級對'dfsSearch'的調用處於執行過程中，但尚未退出其塊，但執行內部/子級對'dfsSearch'的調用並且bam！ – rmirabelle

併發修改是其中一個原因。另外，該算法在List List結果中從根到葉收集「所有路徑」。如果您沒有在遞歸方式下在每個級別創建新列表，那麼在遞歸回滾之後最終會出現一個大混亂列表（從根到葉的所有路徑都收集在一個混合列表中，而不是其中的每個路徑自己的清單）。

來源

2017-03-29 21:36:05 geneSummons

爲什麼在遞歸調用之前實例化一個新列表？

回答

相關問題