Как эта рекурсия и обратное отслеживание работают в LeetCode?

Question

Эта функция выводит узлы связанного списка в обратном порядке:

void recur(ListNode head) {
    if(head == null) return; 
    recur(head.next);
    tmp.add(head.val);
}

Если список 1 -> 2 -> 3 , то tmp (an ArrayList) добавит значение узла.

Наконец, мы можем получить список [3, 2, 1], напечатав tmp. Однако я не знаю, почему это работает. Почему функция recur l oop до последнего узла добавляет значения в обратном порядке?

Answer 1

Я думаю, что эта блок-схема может вам помочь.

Как видно из диаграммы, head.value добавляется в список tmp только когда достигнут конец связанного списка. то есть голова обнуляется

Answer 2

Это довольно просто, давайте рассмотрим узел [1 -> 2] с двумя ListNode, и мы хотим повернуть вместе с вами функцию:

void recur(ListNode head) {
    if (head == null) return;
    recur(head.next);
    tmp.add(head.val);
}

1. На первом стволе голова будет указывать на 1 значение, эта проверка if (head == null) вернет false, так как головной узел не является нулевым.
2. Затем мы вызываем ту же функцию recur, но для следующего узла со значением 2, и выполнение recur начинается заново, но с узлом 2 в качестве головного узла. Мы снова проверяем if (head == null) -> false, по той же причине заголовок здесь не равен нулю.
3. Затем мы вызываем ту же функцию recur, но для следующего узла, который равен нулю head.next -> null, так как больше нет узлов после узла 2. Мы проверяем if (head == null), но теперь у нас есть true, текущий узел, что означает, что после него не осталось узлов, и мы не можем go далее вызывать recur() снова. Итак, мы остановили рекурсию с помощью оператора return.
4. Теперь мы снова вернемся к шагу # 2 и продолжим выполнение, потому что выполнение recur(head.next) заканчивается оператором return. Это означает, что этот узел является последним, и мы помещаем его значение в tmp. И выполнение recur для ListNode 2 заканчивается, так как после кода нет строк кода.
5. Теперь мы снова вернемся к шагу # 1 и выполним ту же логику c, как описано в шаге 4 Поскольку recur для узла 2 завершает его выполнение, мы продолжаем и помещаем значение 1 в массив tmp.

---

if (head == null) return; - эта проверка, называемая рекурсией base case, что означает when we need to end execution and exit?, без нее рекурсия будет go бесконечно.

Копаем до конца ListNode и затем снова возвращаемся наверх. Чтобы иметь возможность поместить значение ListNode в tmp, нам нужно сначала поместить следующее значение в tmp и так далее.

Надеюсь, я объяснил более точно, и теперь это более понятно для вас.