Как узнать
задача на дереве, где важен порядок, в котором встречаются узлы: значения по возрастанию или k-й наименьший в BST (симметричный), копирование или сохранение дерева (прямой), размеры, высоты и удаление (обратный).
Как решать такие задачи
- Выбери порядок по тому, когда узлу нужна своя работа: до потомков (прямой), между ними (симметричный) или после них (обратный).
- Напиши f(node). Если node — none, просто вернись.
- Поставь работу самого узла до, между или после вызовов f(node.left) и f(node.right).
- В BST симметричный обход выдаёт значения по возрастанию: так находят k-й наименьший, проверяют, что дерево — BST, и сравнивают соседей.
Где встречается
- Удаление папки. rm -r не может удалить папку, пока в ней что-то есть, поэтому сначала удаляет содержимое, а папку — после. Это обратный обход.
- Веб-страницы. document.querySelectorAll возвращает элементы в порядке документа: сначала элемент, потом его дети по очереди. Это прямой обход дерева HTML.
- Компиляторы. Чтобы посчитать (2 + 3) × 4, сначала нужны оба операнда, потом операция, поэтому дерево выражения обходят обратным обходом. Байт-код Python так и выглядит: сначала загрузить операнды, потом операция.