Значение параметра рекурсии Java Значение

Question

Из двоичного дерева вы хотите создать 2-й arraylist, где каждый arraylist в основном arraylist содержит все узлы двоичного дерева на одном уровне для всех уровней. Я понимаю, как это сделать рекурсивно с DFS, но я очень смущен тем, почему можно получить правильный ответ, передав в arraylist, который я хочу заполнить как параметр в рекурсивной функции.

Заголовок моей рекурсивной функции выглядит следующим образом

createLevelLinkedList(TreeNode current, ArrayList<LinkedList<TreeNode>> lists, int level) 

С basecase:

if (current == null) return; 

Как дерево проходится, текущий узел будет добавлен в соответствующий ArrayList в «списках» , В рекурсивной функции там есть два рекурсивных вызовов переместить функцию к дочерним узлам тока:

createLevelLinkedList(current.left, lists, level + 1); 
createLevelLinkedList(current.right, lists, level + 1); 

Предположим, что это дерево, которое выглядит следующим образом

  5 
    3   8 
2  4   9 

С глубины первого обхода дерева, после того, как первый возврат, мы получим TreeNode «2» - это верхний объект в стеке, затем «3». Когда TreeNode «3» является текущей и функция вызывает

createLevelLinkedList(current.right, lists, level + 1); 

Протолкнуть TreeNode «4» в стек, как можно списки содержит TreeNode «2», если он на самом деле делает, и что на самом деле происходит в памяти?

код я ссылки можно найти на Github: https://github.com/gaylemcd/ctci/blob/master/java/Chapter%204/Question4_4/QuestionDFS.java

public static void createLevelLinkedList(TreeNode root, ArrayList<LinkedList<TreeNode>> lists, int level) 
{ 
    if (root == null) return; 
    LinkedList<TreeNode> list = null; 
    if (lists.size() == level) { // Level not contained in list 
    list = new LinkedList<TreeNode>(); 
/* Levels are always traversed in order. So, if this is the first time we've visited level i, 
* we must have seen levels 0 through i - 1. We can therefore safely add the level at the end. */ 
    lists.add(list); 
    } else { 
    list = lists.get(level); 
    } 
    list.add(root); 
    createLevelLinkedList(root.left, lists, level + 1); 
    createLevelLinkedList(root.right, lists, level + 1); 
} 

Answer 1

Вы должны понимать, что есть только один ArrayList экземпляр передается методу createLevelLinkedList. Каждый рекурсивный вызов createLevelLinkedList получает ссылку на тот же экземпляр ArrayList.

Поэтому, как только TreeNode 2 добавляют к ArrayList (или, точнее, к одной из LinkedList с содержащимися в ArrayList), он остается там в течение выполнения рекурсивного метода. Он не исчезает, когда возвращается значение createLevelLinkedList, которое добавило его в список.