Где применяется
1. Задача
Открой файловый менеджер. В папках лежат файлы и другие папки, в тех ещё папки, и всё это растёт из одной верхней папки. Ты хочешь что-то сделать с каждым элементом: напечатать его, сложить размеры, найти нужный. Значит, нужно посетить каждый элемент, и ровно один раз.
Такая ветвящаяся структура называется деревом (tree). Каждый элемент это узел (node): в нём хранится значение и ссылки вниз на его детей (children). Единственный узел на самом верху, у которого нет родителя, это корень (root). Ветка комментариев, оргструктура компании, HTML-код страницы: всё это деревья.
Остаётся выбрать порядок обхода. «Показать папку раньше её содержимого» и «показать всех сотрудников уровень за уровнем» это два разных обхода одного дерева, и каждый отвечает на свой вопрос.
Этот шаг из платной части
Бесплатные шаги в начале курса (их 33) открыты всем: урок, задача и тесты. Этот шаг открывается с полным доступом. Начни с бесплатного аккаунта и бесплатных шагов.
Завести бесплатный аккаунтПосмотреть, что входитtraverse(root) // root = [4, 2, 6, 1, 3, 5, 7]Обходим дерево симметрично: левое поддерево, потом узел, потом правое поддерево. Начинаем с корня.
Как узнать
Эти слова в условии значат этот паттерн
- бинарное дерево задано как корневой узел с указателями left/right
- посетить каждый узел (прямой / симметричный / обратный / по уровням)
- посчитать глубину, высоту или сумму по всему дереву
- обработать детей до или после родителя
- вывод по уровням (BFS с очередью)
Похоже, но не то
- Обход графа BFS / DFS (Graph BFS / DFS)
В граф можно попасть в узел дважды, поэтому нужно множество посещённых. В дереве нельзя, поэтому не нужно.
- Рекурсия (Recursion)
Рекурсия это то, чем обход обычно записывают. Эта страница про три порядка посещения.
- Стек (LIFO) (Stack (LIFO))
Итеративный обход меняет стек вызовов на свой. Порядок посещения при этом тот же.
- Двоичное дерево поиска (Binary search tree)
В дереве поиска симметричный обход даёт отсортированные значения. В любом другом дереве этот порядок ничего не значит.
n узлов дают O(n) времени. Память O(h) на стек, а h равно n на вырожденной цепочке.
На LeetCode
Задачи, где нужно посетить каждый узел двоичного дерева в заданном порядке, в глубину или по уровням. Выбери pre-order, in-order, post-order или очередь для обхода по уровням и делай работу в момент посещения.
preorder из урока, сначала узел, потом левое, потом правое.
inorder из урока, и хороший повод написать его ещё и со своим стеком.
bfs из урока, только сначала возьми текущую длину очереди, чтобы каждый уровень попал в свой список.
Обход по уровням через очередь, и с каждого уровня оставляешь последний узел.
Посети каждый узел в любом порядке и поменяй местами его левого и правого ребёнка.