---
title: "Наименьший общий предок"
url: https://algopath.pro/ru/patterns/tree-lca
language: ru
summary: "Наименьший общий предок это самый глубокий узел, под которым лежат обе цели. Найти его хватает одного обратного обхода дерева."
updated: 2026-08-24
---

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

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

## Наименьший общий предок: как это работает?

Задайте каждому узлу один и тот же вопрос. Лежит ли в моём поддереве хоть одна цель?

Пустой узел отвечает нет. Узел, который сам является целью, отвечает собой.

Иначе спросите обоих потомков. Каждый вернёт узел или ничего.

Если ответили оба потомка, предок это текущий узел. Цели расходятся именно здесь.

Если ответил только один, передайте его ответ наверх. Расхождение ещё не случилось.

Первый узел, где ответили обе стороны, и есть самый глубокий. Ничто выше него не может быть ниже.

- `узел 6: найдено` Ищем 6 и 2. Узел 6 отвечает собой.
- `узел 2: найдено` Узел 2 тоже отвечает собой.
- `узел 5: ответили обе стороны` Цели расходятся здесь. Ответ это узел 5.
- `узел 3: ответила только левая` Правое поддерево ничего не нашло. Наверх идёт узел 5.
- `ответ = 5` Один проход по дереву. Ни один узел не посещён дважды.

## Наименьший общий предок: когда применять?

- наименьший общий предок двух узлов
- самый глубокий узел, который является предком и p, и q
- каждый рекурсивный вызов возвращает, какой из целевых узлов найден под ним
- путь от корня до каждого узла и их сравнение (альтернативный подход)
- дано бинарное дерево или BST, найти точку, где расходятся два пути

## Наименьший общий предок: с чем путают?

- **Двоичное дерево поиска** - В дереве поиска направление задают сами значения. В обычном дереве надо спросить оба поддерева.
- **Обход дерева** - Та страница про три порядка посещения. Здесь обратный обход отвечает на один вопрос.
- **Система непересекающихся множеств** - Офлайновый алгоритм Тарьяна отвечает на много пар через непересекающиеся множества. Одной паре это не нужно.
- **DP на деревьях** - Динамика на деревьях поднимает наверх посчитанные значения. Здесь наверх идёт только найдено или нет.

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

n узлов дают O(n) на один запрос. Для многих запросов берут двоичные подъёмы по O(log n).

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

### Предок внутри дерева поиска

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

Узел считается предком самого себя.

Направление подсказывают сами значения.

Если обе цели меньше, идите влево; если обе больше, вправо. Первый узел между ними и есть ответ.

```javascript
function lowestCommonAncestor(root, p, q) {
    let node = root;

    while (node) {
        if (p.val < node.val && q.val < node.val) {
            node = node.left;
        } else if (p.val > node.val && q.val > node.val) {
            node = node.right;
        } else {
            return node; // the values split here, or one of them is this node
        }
    }

    return null;
}
```

## Наименьший общий предок: частые ошибки

- **Ищут каждый узел по отдельности** Два поиска и сравнение путей это заметно больше работы. Один обратный обход отвечает сразу.
- **Забывают, что узел бывает предком себе** Если одна цель лежит над другой, она и есть ответ. Возвращайте узел сразу при совпадении.
- **Считают, что оба узла точно есть** Если одного нет, проход вернёт второй. Проверяйте наличие, когда отсутствие допустимо.
- **Берут приём дерева поиска на обычном дереве** Сравнение значений работает только при гарантированном порядке. Иначе надо спрашивать оба поддерева.

## Наименьший общий предок: задачи с собеседований

- **Наименьший общий предок в двоичном дереве** Чистая форма: один обратный обход.
- **Наименьший общий предок в дереве поиска** Направление задают одни только значения.
- **Предок при наличии ссылок на родителя** Поднимайтесь от обоих узлов и встретьтесь.
- **Предок самых глубоких листьев** Несите наверх глубину вместе с узлом.
- **Расстояние между двумя узлами** Обе глубины минус удвоенная глубина предка.
- **Наименьшее поддерево со всеми глубокими узлами** Та же форма, только цели другие.
- **Пошаговый маршрут между узлами** Найдите предка, потом постройте оба пути.

## JavaScript

```javascript
function lca(node, p, q) {
    if (!node || node === p || node === q) return node;
    const left = lca(node.left, p, q);
    const right = lca(node.right, p, q);
    if (left && right) return node; // p and q split here
    return left || right;
}
```

## Python

```python
def lca(node, p, q):
    if not node or node is p or node is q:
        return node
    left = lca(node.left, p, q)
    right = lca(node.right, p, q)
    if left and right:
        return node  # p and q split here
    return left or right
```

## PHP

```php
function lca(?TreeNode $node, TreeNode $p, TreeNode $q): ?TreeNode {
    if ($node === null || $node === $p || $node === $q) return $node;
    $left = lca($node->left, $p, $q);
    $right = lca($node->right, $p, $q);
    if ($left !== null && $right !== null) return $node; // split point
    return $left ?? $right;
}
```