Задачи на деревья на собеседовании: разбор типовых

Коротко

Деревья дают почти на каждом собеседовании. Хорошая новость: 80% задач решаются одним из трёх обходов.

База: три обхода в глубину

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def inorder(node, out):      # левое → корень → правое
    if node:
        inorder(node.left, out)
        out.append(node.val)
        inorder(node.right, out)


def preorder(node, out):     # корень → левое → правое
    if node:
        out.append(node.val)
        preorder(node.left, out)
        preorder(node.right, out)


def postorder(node, out):    # левое → правое → корень
    if node:
        postorder(node.left, out)
        postorder(node.right, out)
        out.append(node.val)

Разница в одной строке — где стоит append. Но применения разные:

• inorder на дереве поиска даёт отсортированную последовательность — это ключ ко многим задачам;
• preorder — копирование и сериализация дерева;
• postorder — вычисления снизу вверх: удаление, подсчёт размеров, высота.

Правило: если ответ для узла зависит от детей — это postorder.

Обход по уровням

from collections import deque

def level_order(root) -> list[list[int]]:
    if not root:
        return []

    result = []
    queue = deque([root])

    while queue:
        level = []
        for _ in range(len(queue)):     # фиксируем размер уровня
            node = queue.popleft()
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(level)

    return result

Ключевая деталь — for _ in range(len(queue)). Она фиксирует количество узлов текущего уровня до того, как мы начнём добавлять следующий. Без неё уровни смешаются.

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

Глубина дерева

def max_depth(root) -> int:
    if not root:
        return 0
    return 1 + max(max_depth(root.left), max_depth(root.right))

Три строки, но проговорите: сложность O(n), память O(h), где h — высота. Для сбалансированного дерева это O(log n), для вырожденного — O(n).

Минимальная глубина: ловушка

def min_depth(root) -> int:
    if not root:
        return 0

    # если ребёнок один, нельзя брать min — придём к нулю через пустую ветку
    if not root.left:
        return 1 + min_depth(root.right)
    if not root.right:
        return 1 + min_depth(root.left)

    return 1 + min(min_depth(root.left), min_depth(root.right))

Наивный 1 + min(...) даёт неверный ответ на дереве-цепочке: пустая ветка вернёт 0, и минимум станет 1. Это классический вопрос-ловушка.

Симметричность

def is_symmetric(root) -> bool:
    def mirror(a, b) -> bool:
        if not a and not b:
            return True
        if not a or not b:
            return False
        return (a.val == b.val
                and mirror(a.left, b.right)      # зеркально!
                and mirror(a.right, b.left))

    return not root or mirror(root.left, root.right)

Суть в перекрёстном сравнении: левое одного с правым другого. Частая ошибка — сравнивать a.left с b.left, что проверяет равенство, а не зеркальность.

Проверка дерева поиска

def is_valid_bst(root) -> bool:
    def check(node, low, high) -> bool:
        if not node:
            return True
        if not (low < node.val < high):
            return False
        return (check(node.left, low, node.val)
                and check(node.right, node.val, high))

    return check(root, float('-inf'), float('inf'))

Главная ловушка темы. Наивная проверка «левый ребёнок меньше, правый больше» неверна:

        5
       / \
      3   8
         / \
        2   9     ← 2 меньше 5, но лежит в правом поддереве

Локально всё правильно, но дерево не является деревом поиска. Нужны именно границы, которые сужаются при спуске.

Альтернатива: inorder-обход должен дать строго возрастающую последовательность.

Наименьший общий предок

В дереве поиска

def lca_bst(root, p, q):
    while root:
        if p.val < root.val and q.val < root.val:
            root = root.left
        elif p.val > root.val and q.val > root.val:
            root = root.right
        else:
            return root         # разошлись — это и есть предок

Используем упорядоченность: как только узлы оказались по разные стороны, мы нашли ответ.

В обычном дереве

def lca(root, p, q):
    if not root or root is p or root is q:
        return root

    left = lca(root.left, p, q)
    right = lca(root.right, p, q)

    if left and right:
        return root             # узлы в разных поддеревьях
    return left or right

Элегантное решение, которое стоит понять, а не заучить: если оба потомка вернули непустое значение, значит искомые узлы в разных ветках, и текущий узел — их общий предок.

Пройди собеседование в топ-компанию

Платформа для подготовки

Решай алгоритмические задачи как профи

✓ Популярные алгоритмы✓ Разбор решений✓ AI помощь

Начать сейчас→

Рекурсия или итерация

На интервью почти всегда достаточно рекурсии — она короче и понятнее. Но стоит знать ограничение и уметь ответить на вопрос «а если дерево глубокое?».

Итеративный inorder через стек:

def inorder_iterative(root) -> list[int]:
    result, stack = [], []
    current = root

    while current or stack:
        while current:
            stack.append(current)
            current = current.left
        current = stack.pop()
        result.append(current.val)
        current = current.right

    return result

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

Что уточнять

• Дерево двоичное или произвольной арности?
• Это дерево поиска?
• Могут ли значения повторяться?
• Есть ли ссылка на родителя?
• Гарантирована ли сбалансированность?

Последние два меняют решение принципиально. Ссылка на родителя, например, упрощает поиск общего предка до подъёма по цепочкам.

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

Отсутствие базового случая. if not node: return — первая строка почти любой рекурсии по дереву.

Локальная проверка дерева поиска. Разобрано выше, самая частая ошибка темы.

Смешивание уровней в BFS. Забытая фиксация len(queue).

Наивный минимум глубины. Пустая ветка ломает ответ.

Сравнение по значению вместо ссылки при поиске узлов. Значения могут повторяться.

Забытая оценка памяти. Рекурсия расходует стек глубиной с высоту дерева — это часть ответа про сложность.

Что запомнить

• Три обхода отличаются одной строкой, но применения разные: inorder для деревьев поиска, postorder для вычислений снизу вверх.
• В обходе по уровням фиксируйте размер очереди перед обработкой уровня.
• Проверка дерева поиска требует границ, а не локального сравнения с детьми.
• Минимальная глубина — ловушка с пустой веткой.
• Рекурсия расходует O(высоты) памяти; на глубоких деревьях нужен явный стек.
• Уточняйте, есть ли ссылка на родителя и возможны ли дубликаты.