Выбор ответа Junior Деревья спрашивают часто обновлено
Обход по уровням
Вопрос
Нужно вернуть значения дерева по уровням: [[3], [9, 20], [15, 7]]. Какой обход?
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: BFS с очередью, уровень по её размеру. BFS идёт волнами.
Варианты ответа
- DFS pre-order с записью значений по порядку
- In-order: он выдаёт узлы слева направо
- BFS с очередью, уровень по её размеруправильный ответ
- Post-order, затем развернуть результат
Разбор
BFS идёт волнами. Перед обработкой уровня запоминаем size = queue.length и снимаем ровно столько узлов: так узлы разных уровней не перемешаются. O(n).
- DFS тоже можно, если передавать глубину, но естественный и ожидаемый ответ BFS.
- In-order и post-order не группируют по уровням.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.