Мы используем необходимые куки для работы сайта (вход и язык). Если ты согласишься, мы также загрузим Google Analytics, чтобы видеть, какие страницы читают, и Google reCAPTCHA для защиты форм обратной связи и сообщений об ошибке от спама. Политика конфиденциальности

← Блог
Как готовиться

Наименьший общий предок: одна рекурсия для дерева и один спуск для дерева поиска

· 2026-11-12

Короткий ответ. Наименьший общий предок двух узлов это самый глубокий узел, под которым лежат оба. Для обычного двоичного дерева он ищется одним обходом в глубину за O(n). Для дерева поиска хватает одного спуска за O(h). Ниже идея, код на Python для обоих случаев, разбор на примере и другие варианты.

Что такое наименьший общий предок?

Предок узла это любой узел на пути от корня до него. Общий предок двух узлов лежит на обоих путях. Наименьший это самый глубокий из общих, тот, что дальше всех от корня.

Узел считается предком самого себя. Если p лежит в поддереве q, ответ это q.

Наивный способ: найти путь от корня до p, путь до q и сравнить их. Последний общий узел и есть ответ. Работает, но требует два списка и два обхода.

Задача сокращённо называется LCA. Она встречается сама по себе и как шаг в задачах про расстояние.

Наименьший общий предок двух узлов
lca(root, 6, 4) // root = [3, 5, 1, 6, 2, 0, 8, null, null, 7, 4]
→ над узлом = что вернул этот вызов
p = 6q = 4node = -

Ищем наименьшего общего предка p = 6 и q = 4. Каждый вызов задаёт один вопрос: есть ли цель в моём поддереве?

Страница паттерна: когда его применять и шаблон на шести языках

Как ищется наименьший общий предок в двоичном дереве?

Рекурсия. Функция возвращает p или q, если встретила их. Иначе она возвращает None. Спрашиваем левое и правое поддерево.

Оба вернули не None, значит p и q по разные стороны. Текущий узел и есть ответ. Один вернул не None, пробрасываем его наверх. Оба None, возвращаем None.

Одна функция, один проход, O(n) по времени и O(h) по стеку.

Как это выглядит на примере?

Дерево: корень 3, слева 5, справа 1. У 5 дети 6 и 2. У 2 дети 7 и 4. Ищем предка 7 и 4.

Из 3 идём в 5, из 5 в 6: там ничего, None. Из 5 в 2. Из 2 в 7: это p, возвращаем 7. Из 2 в 4: это q, возвращаем 4. В узле 2 оба не None, ответ 2. Наверх до корня пробрасывается 2.

Ищем предка 5 и 4. Узел 5 это p, возвращаем его сразу, не спускаясь. Правое поддерево корня даёт None. Ответ 5, потому что 4 лежит под ним.

Как написать поиск наименьшего общего предка на Python?

def lca(root, p, q):
    if root is None 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                 # p и q по разные стороны
    return left or right

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_with_parent(p, q):
    a, b = p, q                     # как пересечение двух списков
    while a is not b:
        a = a.parent if a else q
        b = b.parent if b else p
    return a

Третья функция работает, когда у узлов есть ссылка на родителя. Два указателя идут вверх и меняются местами в конце. Это тот же приём, что в пересечении двух связных списков.

Чем варианты задачи отличаются друг от друга?

ВариантЧто даноСпособВремя
Двоичное деревоКорень, p и q точно естьРекурсия с пробросомO(n)
Дерево поискаКорень, правило слева меньшеОдин спускO(h)
Ссылки на родителяТолько p и qДва указателя вверхO(h)
p или q может отсутствоватьКореньРекурсия плюс счётчик найденныхO(n)
Много запросовДерево на миллион узловДвоичный подъём, предподсчётO(log n) на запрос

Как найти предка в дереве поиска?

Оба значения меньше узла, оба предка слева, идём влево. Оба больше, идём вправо. Иначе значения разошлись, или узел равен одному из них. Это и есть ответ.

Рекурсия не нужна, хватает цикла. Память O(1).

Здесь правило дерева поиска заменяет целый обход. В обычном дереве мы не знаем, где искать p и q. В дереве поиска значения сами говорят, куда идти.

Как посчитать расстояние между двумя узлами?

Расстояние это глубина p плюс глубина q минус удвоенная глубина их предка. Находим предка, считаем три глубины. Всё за один или два обхода.

По каким словам в задаче узнать приём?

  • «Наименьший общий предок», «lowest common ancestor».
  • «Расстояние между двумя узлами дерева».
  • «Самое глубокое поддерево, содержащее оба узла».
  • «Общий менеджер двух сотрудников» в дереве подчинения.

На каких ошибках ломается решение?

  • Сравнивают значения вместо узлов. Два узла могут хранить одно значение.
  • Считают, что p и q всегда есть в дереве. Условие может говорить иное.
  • Спускаются в дерево поиска рекурсией на всю глубину вместо цикла.
  • Ищут оба пути от корня и сравнивают списки. Верно, но O(n) памяти зря.

Как объяснить приём на собеседовании?

Скажите: функция возвращает найденный узел или None. Узел с двумя непустыми ответами это предок. Одна фраза, и логика ясна. Назовите O(n).

Спросят про дерево поиска, покажите спуск за O(h). Спросят про ссылки на родителя, покажите два указателя.

Отработать узнавание приёма можно на странице наименьший общий предок. Обходы разобраны на странице обход дерева.

Вопросы и ответы

Что делать, если p или q нет в дереве?

Считайте, сколько из них нашлось, отдельным счётчиком. В конце проверьте, что нашлись оба. Иначе верните None.

Как отвечать на миллион запросов быстро?

Двоичный подъём. Для каждого узла заранее считаем предка на 1, 2, 4 и 8 шагов вверх. Запрос отвечается за O(log n). Предподсчёт O(n log n).

Работает ли рекурсия для дерева с произвольным числом детей?

Да. Вместо left и right перебираем всех детей. Считаем, сколько вернули не None. Два и больше, текущий узел предок.

Где наименьший общий предок встречается в реальных системах?

В git при слиянии веток: merge base это общий предок двух коммитов. В файловых системах при поиске общей папки. В иерархиях классов при поиске общего родителя.