Алгоритмы с нуля
Рекурсия на деревьях
Вы знаете три способа ходить по дереву: прямой, симметричный, обратный. Но ходить — это не решать. Чтобы решить задачу на дереве — найти высоту, подсчитать узлы, проверить, сбалансировано ли оно — нужно думать как дерево. Дерево это узел с двумя поддеревьями. Поэтому чтобы решить для узла, задай один и тот же вопрос обоим поддеревьям, потом скомбинируй их ответы с собственным значением узла. Это рекурсия на деревьях, и это самый мощный инструмент для задач на деревьях.
После этого урока вы сможете писать рекурсивные функции для решения задач на деревьях, работая снизу вверх (постorder), распознавать и реализовывать паттерн «рекурсируй на поддеревьях и комбинируй», трассировать рекурсивную функцию дерева, чтобы проверить её корректность, объяснять, почему возврат значения от каждого поддерева — ключ к решению задачи, и выбирать правильный базовый случай (пустое поддерево) и правило комбинирования для вашей задачи.
Что означает «рекурсия на деревьях»?
Рекурсия на деревьях — это способ решать задачи, где вы:
- Решаете задачу для левого поддерева (рекурсивно).
- Решаете задачу для правого поддерева (рекурсивно).
- Комбинируете оба ответа с информацией о текущем узле.
- Возвращаете комбинированный результат вверх по стеку вызовов.
Ключевая идея: дерево — это просто узел с двумя поддеревьями. Поэтому предположи, что твоя функция уже работает на поддеревьях, и построй ответ для текущего узла из этих результатов.
Базовый случай: пустое поддерево
Каждая рекурсивная функция дерева нуждается в базовом случае. В задачах на деревья базовый случай — это когда поддерево равно null (пусто). В этой точке ты возвращаешь значение, что имеет смысл для твоей задачи — часто 0 для подсчётов или -1 для высот.
Комбинирование результатов: мышление постorder
Порядок, в котором ты посещаешь дерево, имеет значение. Чтобы комбинировать результаты из поддеревьев с текущим узлом, ты должен:
- Рекурсивно получить левый результат.
- Рекурсивно получить правый результат.
- Комбинировать их с текущим узлом.
Это postorder: левое поддерево, правое поддерево, потом сам узел.
Ментальная модель
Думай о рекурсии как о сообщениях, текущих ВВЕРХ по дереву:
- Каждый лист отправляет вверх своё базовое значение.
- Каждый внутренний узел спрашивает обоих детей «какой ответ на твоё поддерево?», потом комбинирует ответы и отправляет результат вверх своему родителю.
- Корень возвращает ответ для всего дерева.
Пример 1: Вычисление высоты дерева
Высота дерева — это самый длинный путь от корня до листа.
Рекурсивная идея: высота узла = 1 + max(высота левого поддерева, высота правого поддерева).
1
function height(node) {
2
// Базовый случай: пустое дерево
3
if (node === null) return -1;
4
5
// Рекурсивный случай: спроси оба поддерева за их высоты
6
const leftHeight = height(node.left);
7
const rightHeight = height(node.right);
8
9
// Комбинируй: возьми макс и добавь 1
10
return 1 + Math.max(leftHeight, rightHeight);
11
}
- L1 Функция вычисляет высоту поддерева, корень которого node.
- L3 Базовый случай: пустое дерево имеет высоту -1. Это делает математику рабочей: высота одного узла = 1 + max(-1, -1) = 0.
- L6 Рекурсивно спроси левое поддерево за его высоту.
- L7 Рекурсивно спроси правое поддерево за его высоту.
- L10 Комбинируй: высота этого узла — это 1 плюс высота более высокого поддерева.
Пример: Для дерева:
1
/ \
2 3
/
4height(4)это лист: его два null ребёнка каждый возвращает -1, поэтому он возвращает 1 + max(-1, -1) = 0. Узел 4 имеет высоту 0.height(2)спрашивает height(4) и height(null), получает 0 и -1, возвращает 1 + max(0, -1) = 1. Узел 2 имеет высоту 1.height(3)это лист: возвращает 1 + max(-1, -1) = 0. Узел 3 имеет высоту 0.height(1)спрашивает height(2) и height(3), получает 1 и 0, возвращает 1 + max(1, 0) = 2. Дерево имеет высоту 2.
Пример 2: Подсчёт узлов в дереве
Подсчёт узлов: count = 1 (для этого узла) + count левого поддерева + count правого поддерева.
1
function countNodes(node) {
2
// Базовый случай: пустое дерево имеет 0 узлов
3
if (node === null) return 0;
4
5
// Рекурсивный случай: спроси оба поддерева за их подсчёт узлов
6
const leftCount = countNodes(node.left);
7
const rightCount = countNodes(node.right);
8
9
// Комбинируй: 1 (текущий узел) + левый + правый
10
return 1 + leftCount + rightCount;
11
}
- L1 Функция возвращает число узлов в поддереве, корень которого node.
- L3 Базовый случай: пустое дерево имеет 0 узлов.
- L6 Рекурсивно подсчитай узлы в левом поддереве.
- L7 Рекурсивно подсчитай узлы в правом поддереве.
- L10 Комбинируй: добавь 1 для текущего узла плюс все узлы в обоих поддеревьях.
Пример: Для того же дерева:
countNodes(4)это лист: его null ребёнка каждый возвращает 0, поэтому он возвращает 1 + 0 + 0 = 1.countNodes(2)спрашивает countNodes(4) и countNodes(null), получает 1 и 0, возвращает 1 + 1 + 0 = 2. Поддерево с корнем 2 имеет 2 узла.countNodes(3)возвращает 1 + 0 + 0 = 1. Поддерево с корнем 3 имеет 1 узел.countNodes(1)спрашивает countNodes(2) и countNodes(3), получает 2 и 1, возвращает 1 + 2 + 1 = 4. Всё дерево имеет 4 узла.
Запуск обеих функций на конкретном дереве
1
let root = new Node(1, new Node(2, new Node(4)), new Node(3));
2
height(root);
1
let root = new Node(1, new Node(2, new Node(4)), new Node(3));
2
countNodes(root);
Сложность по времени
Обе функции height и countNodes посещают каждый узел в дереве ровно один раз. Каждый узел обрабатывается один раз: мы вычисляем максимум (для высоты) или добавляем подсчёт (для подсчёта узлов) за O(1) времени. Для дерева с n узлами, сложность по времени — O(n).
Сложность по памяти
Место приходит из стека вызовов рекурсии. В худшем случае, глубина стека вызовов равна высоте дерева. В сбалансированном дереве высота O(log n). В перекошенном дереве (как связный список) высота O(n). Поэтому сложность по памяти — O(h), где h — высота дерева.
Для дерева со структурой: 5 / \ 3 7 / / \ 2 6 8 Какова высота дерева?
В функции height, почему мы возвращаем -1 для пустого поддерева вместо 0?
Для countNodes, что возвращает каждый рекурсивный вызов?
Когда вы вызываете height на корне дерева высоты 2, какое поддерево исследуется первым?
Какова сложность по памяти функции height для перекошенного двоичного дерева (где каждый узел имеет только правого ребёнка)?
lesson.inset.undefined
Почему рекурсия на деревьях? Итеративные решения на деревьях часто требуют стека или очереди, чтобы отслеживать узлы, которые вы ещё не обработали. Рекурсия делает это отслеживание для вас, используя стек вызовов. Она также совпадает с структурой дерева: дерево — это узел плюс два поддерева, поэтому рекурсивная структура отражает структуру данных.
lesson.inset.undefined
Пустые деревья и одиночные узлы. Если корень null, базовый случай возвращает немедленно. Если дерево это одиночный узел, оба ребёнка null, рекурсивные вызовы попадают в базовый случай, и вы комбинируете базовые значения с текущим узлом. Никакой специальной обработки не нужно.
lesson.inset.undefined
Трассируй руками. Нарисуй маленькое дерево (3–4 узла). Выбери задачу (высота, подсчёт или простое свойство). Выполни рекурсию руками: при каждом вызове, отметь рекурсивные вызовы, жди их возвращения, потом комбинируй. Смотри, как значения текут вверх по дереву. Это строит интуицию.
Какова ключевая идея, что делает рекурсию на деревьях рабочей?
Рекурсия на деревьях решает задачи, задавая один и тот же вопрос к обоим поддеревьям, комбинируя их ответы с текущим узлом, и возвращая комбинированный результат. Базовый случай — всегда пустое поддерево (null). Два рабочих примера — высота и countNodes — показывают паттерн: предположи, что оба поддерева возвращают значение, скомбинируй эти значения с информацией о текущем узле (max для высоты, сумма для подсчёта), и возвращай результат. Сложность по времени O(n) (посетить каждый узел один раз). Сложность по памяти O(h) (глубина стека рекурсии = высота дерева). Этот паттерн расширяется на любую задачу на дереве: проверить свойство, суммировать значения, найти максимум и т.д. Следующий урок охватывает двоичные деревья поиска: деревья с конкретным свойством (значения в левом поддереве меньше, значения в правом больше), что позволяет искать за O(log n) времени.