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

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

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

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

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

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

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

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

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

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

interface TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
}

function lca(node: TreeNode | null, p: TreeNode, q: TreeNode): TreeNode | null {
    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;
}

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

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

    public static TreeNode lca(TreeNode node, TreeNode p, TreeNode q) {
        if (node == null || node == p || node == q) return node;
        TreeNode left = lca(node.left, p, q);
        TreeNode right = lca(node.right, p, q);
        if (left != null && right != null) return node; // p and q split here
        return left != null ? left : right;
    }

    public static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;
    }

    public static TreeNode Lca(TreeNode node, TreeNode p, TreeNode q) {
        if (node == null || node == p || node == q) return node;
        TreeNode left = Lca(node.left, p, q);
        TreeNode right = Lca(node.right, p, q);
        if (left != null && right != null) return node; // p and q split here
        return left ?? right;
    }

    public class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode 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» или «каждый рекурсивный вызов возвращает, какой из целевых узлов найден под ним». Решение на нём обычно укладывается в O(n).

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

Слова в условии для всех паттернов собраны в одной таблице: шпаргалка по паттернам алгоритмов.

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

Паттерн «Наименьший общий предок» чаще всего путают с этими паттернами: Двоичное дерево поиска, Обход дерева, Система непересекающихся множеств и DP на деревьях.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

У паттерна «Наименьший общий предок» целевая сложность O(n).

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