Бинарные деревья и рекурсия

Дерево — это семья

Представь генеалогическое дерево, только перевёрнутое: на самом верху один предок, у него дети, у детей свои дети. В бинарном дереве у каждого «родителя» не больше двух детей: левый и правый.

Основные слова, которые будут звучать на собесе:

• Узел — один элемент дерева: значение и ссылки на детей.
• Корень — самый верхний узел. Родителей у него нет.
• Лист — узел без детей, «конец ветки».
• Поддерево — любой узел вместе со всеми его потомками. Это тоже полноценное дерево.
• Высота — число узлов на самом длинном пути от корня до листа.

Посмотри на подсвеченную часть. Узел 3 со своими детьми 1 и 6 выглядит как обычное маленькое дерево. На этом свойстве держится вся работа с деревьями: любое дерево — это корень плюс два поддерева, а каждое поддерево тоже дерево. Высота этого дерева равна 3, например по пути 8 → 3 → 1.

Высоту иногда считают в рёбрах, а не в узлах. Тогда у дерева на схеме она равна 2. На собесе уточни, какое определение имеется в виду. В задачах вида «максимальная глубина» обычно считают узлы.

Как выглядит узел в коде

Узел хранит значение и две ссылки на детей. Если ребёнка нет, ссылка пустая: None, null или nullptr.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val      # значение узла
        self.left = left    # левый ребёнок (или None)
        self.right = right  # правый ребёнок (или None)

Как думать рекурсивно: «доверься рекурсии»

Новички часто пытаются мысленно прокрутить рекурсию на всю глубину, держат в голове десяток вызовов и путаются. Так делать не нужно.

Представь, что ты начальник отдела. Тебе нужно узнать что-то про всё дерево. Ты не обходишь его сам, а говоришь двум заместителям: «Ты разберись с левым поддеревом, ты с правым, и принесите мне ответ». Потом объединяешь их ответы со своим узлом. Как заместители справятся, тебя не волнует: они устроены так же, как ты.

Любая рекурсивная функция на дереве собирается из трёх вопросов:

Вопрос	Что ответить
Базовый случай	Что вернуть для пустого дерева (null)?
Доверие	Допустим, функция уже правильно работает для левого и правого поддерева.
Сборка	Как из двух ответов и текущего узла получить ответ для всего дерева?

Базовым случаем почти всегда удобно сделать пустой узел, а не лист. Тогда не нужно отдельно разбирать ситуацию «левый ребёнок есть, правого нет»: пустые ветки обработаются сами.

Пример: высота дерева

Пройдём по трём вопросам:

1. Базовый случай: у пустого дерева высота 0.
2. Доверие: height(left) и height(right) уже вернули правильные высоты поддеревьев.
3. Сборка: высота дерева — это высота более высокого поддерева плюс один узел, текущий корень. Получаем 1 + max(left, right).

Это вся логика. Вот как это выглядит в коде:

def height(root):
    if root is None:          # базовый случай: пустое дерево
        return 0
    left = height(root.left)  # доверяем рекурсии
    right = height(root.right)
    return 1 + max(left, right)  # собираем ответ

Проверим на нашем дереве. Поддерево с корнем 3 имеет высоту 2, поддерево с корнем 10 тоже 2 (путь 10 → 14). Получаем 1 + max(2, 2) = 3. Сходится.

Сложность

• Время — O(n): функция заходит в каждый узел ровно один раз.
• Память — O(h), где h — высота дерева. Столько вызовов одновременно лежит в стеке. У сбалансированного дерева h ≈ log n. У вырожденного дерева, похожего на список, h = n.

Как это звучит на собесе

«Решаю рекурсивно. Базовый случай: пустой узел, высота 0. Иначе считаю высоты левого и правого поддеревьев и возвращаю максимум плюс один. Каждый узел посещаю один раз, это O(n) по времени. По памяти O(h) на стек вызовов, в худшем случае O(n) для дерева-цепочки».

Отдельно назови, что такое h, и оцени худший случай. Интервьюеры это ценят.

Частые ошибки

• Нет базового случая или он неверный. Без проверки на null программа упадёт при обращении к root.left.
• Базовый случай на листе вместо пустого узла. Код разрастается проверками вида «а если есть только левый ребёнок?».
• Путаница узлов и рёбер. Отсюда ответ, отличающийся на единицу. Договорись об определении заранее.
• Забытый +1. Без него текущий узел не учитывается, и функция всегда возвращает 0.
• Попытка отследить все вызовы в голове. Достаточно проверить базовый случай и сборку, остальное сделает рекурсия.

Этот шаблон из трёх вопросов (база, доверие, сборка) подходит для большинства задач на деревья: сумма узлов, поиск значения, проверка симметрии. Дальше в практике ты будешь применять его снова и снова, и с каждой задачей это пойдёт быстрее.