Как сохранить путь при обходе дерева для обратного прохода?

Что проверяют

Умеете ли вы вести путь от корня к текущему узлу и откатывать его при возврате, то есть понимаете ли бэктрекинг. Следом обычно просят итеративный вариант или спрашивают, что будет на вырожденном дереве глубиной в миллион узлов.

Как отвечать

Базовый приём: рекурсивный DFS с одной общей коллекцией пути. При входе в узел он добавляется в конец, при выходе удаляется, и в каждый момент коллекция содержит ровно путь от корня до текущего узла.

• общий путь: Deque<Integer> path = new ArrayDeque<>(), path.addLast(node.val) при входе и path.removeLast() после обхода детей. ArrayDeque лучше устаревшего Stack, который наследует синхронизированный Vector;
• фиксация результата: когда путь нужен (дошли до листа, совпала сумма), сохраняют копию new ArrayList<>(path);
• итеративный вариант: в стек кладут пару «узел и путь до него». Просто, но копия пути на каждом узле даёт O(n·h) памяти;
• карта родителей: при обходе записывают parent.put(child, node), а путь восстанавливают от найденного узла вверх и разворачивают через Collections.reverse. Лучший выбор, когда нужен путь к одному целевому узлу;
• итеративный postorder: при обходе с явным стеком сам стек в каждый момент совпадает с путём от корня.

Рекурсивный вариант стоит O(n) по времени и O(h) по памяти, где h высота дерева. На сбалансированном дереве это логарифм, на вырожденном дереве-«списке» h равно n, и рекурсия упирается в StackOverflowError. Тогда нужен явный стек. Увеличенный -Xss лечит симптом, а не причину.

Где спотыкаются

Добавляют в результат сам path, а не копию. К концу обхода список пуст, и все найденные пути оказываются одинаковыми.

Выходят из рекурсии ранним return до удаления узла. В пути остаётся лишний элемент, и следующие ветки считаются неверно.

Хранят путь как List<Integer> и пишут path.remove(node.val). Для такого списка вызов remove(int) удаляет элемент по индексу, а не по значению: получится либо чужой узел, либо IndexOutOfBoundsException. Удалять нужно последний элемент, в Java 21 для этого у List есть removeLast().