Как изменить алгоритм обхода дерева в глубину, чтобы получить обход в ширину

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

Видите ли вы, что DFS и BFS отличаются только структурой, в которой ждут своей очереди узлы. Следом почти всегда просят вывести дерево по уровням или объяснить, почему BFS находит кратчайший путь в невзвешенном графе.

Как отвечать

Покажите переход через итеративную версию. Рекурсивный DFS прячет стек в стеке вызовов, поэтому сначала его делают явным: Deque<TreeNode> как стек, push корня, в цикле pop, обработка узла, push детей (правого раньше левого, чтобы левый вышел первым). Теперь достаточно заменить стек на очередь: offer вместо push, poll вместо pop, детей добавлять слева направо. Узлы начнут выходить в порядке добавления, то есть уровень за уровнем.

Что стоит проговорить сверху:

• структура данных: ArrayDeque, а не LinkedList и тем более не устаревший синхронизированный Stack. ArrayDeque быстрее, но не принимает null, поэтому пустых детей в очередь не кладут;
• обход по уровням: в начале каждой итерации внешнего цикла запомните int size = queue.size() и снимите ровно столько узлов. Так получается List<List<Integer>> и решаются задачи вроде минимальной глубины или зигзага;
• сложность: время O(n) у обоих. Память у DFS O(h) по высоте, у BFS O(w) по ширине, а у полного двоичного дерева последний уровень это около половины узлов;
• граф вместо дерева: нужен visited, и помечать узел надо в момент добавления в очередь, а не при извлечении.

Если спросят, какой обход выбрать: кратчайший путь по числу рёбер и ближайший подходящий узел даёт BFS, а на глубоком узком дереве DFS экономнее по памяти.

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

Пытаются получить BFS из рекурсивного DFS, переставляя строки. Рекурсия всегда даёт стек, без явной очереди обход в ширину не получится.

Помечают узел графа посещённым только при извлечении из очереди. Тогда один узел попадает в очередь несколько раз, и на плотном графе она раздувается.

Забывают, что рекурсивный DFS на вырожденном дереве в сотню тысяч узлов падает со StackOverflowError, а итеративный нет. Это хороший повод объяснить, зачем вообще нужна итеративная версия.