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

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

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

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

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

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

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

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

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

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;
}

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

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

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

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

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

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

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;
}

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

Эти формулировки в условии ведут сюда:

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

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

• Двоичное дерево поиска (Binary search tree): В дереве поиска направление задают сами значения. В обычном дереве надо спросить оба поддерева.
• Обход дерева (Tree traversal): Та страница про три порядка посещения. Здесь обратный обход отвечает на один вопрос.
• Система непересекающихся множеств (Union-find (disjoint set)): Офлайновый алгоритм Тарьяна отвечает на много пар через непересекающиеся множества. Одной паре это не нужно.
• DP на деревьях (DP on trees): Динамика на деревьях поднимает наверх посчитанные значения. Здесь наверх идёт только найдено или нет.

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

• Ищут каждый узел по отдельности

  Два поиска и сравнение путей это заметно больше работы. Один обратный обход отвечает сразу.

• Забывают, что узел бывает предком себе

  Если одна цель лежит над другой, она и есть ответ. Возвращайте узел сразу при совпадении.

• Считают, что оба узла точно есть

  Если одного нет, проход вернёт второй. Проверяйте наличие, когда отсутствие допустимо.

• Берут приём дерева поиска на обычном дереве

  Сравнение значений работает только при гарантированном порядке. Иначе надо спрашивать оба поддерева.

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

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

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

O(n)

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