再帰呼び出しの前に新しいリストをインスタンス化するのはなぜですか？

Question

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を使う方法です。私の質問は、再帰呼び出しの上の2行で、なぜ新しいリストをインスタンス化する必要があるのですか？この一時リスト（temp）を再帰呼び出しに渡すと、curr（関数の引数）を使用できないのはなぜですか？

Answer 1

が、これは

 1 
    2 3 
    4 5 

のは、あなたがtempを使用していなかったとしましょう、あなたのバイナリツリー

で想像してみてください。次に、バイナリツリーの左側を再帰して、currが1,2、および4を追加することを意味します。リストは変更可能なので、それらの値は再帰呼び出しからポップしても再帰呼び出しに保存されます。したがって、currに4を加えた後、ノード2に戻り、右に移動して5を追加します。したがって、currには、1,2,4および1,2が必要です、5。

Answer 2

dfsSearchメソッドが再帰的に呼び出されたときに、currの同時変更を防止するためのコピーです。最初の行curr.add(String.valueOf(root.val));はcurrコレクションを変更しますが、コレクションを変更しながらコレクションをループすることはできません。

Answer 3

同時変更がその理由の1つです。さらに、このアルゴリズムは、List of Lists結果のルートからリーフまでの "すべてのパス"を収集します。再帰的な方法で各レベルで新しいリストを作成しなかった場合は、再帰バブルアップ後に大きな混乱を招くリストが1つ作成されます（ルートからリーフまでのすべてのパスが、自分のリスト）。