Как оптимизировать алгоритм поиска наименьшего общего предка с O(n^2) до O(n)

Что проверяют

Умеете ли вы увидеть, что наивное решение ищет одно и то же много раз, и заменить его одним обходом. Следом почти всегда спрашивают: а если запросов миллион на одном дереве, и что будет на вырожденном дереве в Java.

Как отвечать

Сначала объясните, откуда O(n²): для каждого узла проверяем, лежат ли оба искомых узла в его поддереве, а каждая такая проверка стоит O(n).

O(n) даёт один рекурсивный обход снизу вверх:

TreeNode lca(TreeNode node, TreeNode p, TreeNode q) {
    if (node == null || node == p || node == q) return node;
    TreeNode l = lca(node.left, p, q);
    TreeNode r = lca(node.right, p, q);
    if (l != null && r != null) return node;
    return l != null ? l : r;
}

Каждый узел посещается один раз: время O(n), память O(h) на стек, где h высота дерева. Если оба поддерева вернули непустой результат, текущий узел и есть общий предок. Если p сам предок q, функция вернёт p, и это верный ответ.

Дальше покажите, что знаете варианты:

• BST: порядок ключей позволяет спускаться от корня без обхода всего дерева, O(h);
• есть ссылки на родителя: выровнять глубину и подниматься парой, O(h) и O(1) памяти, или сложить предков p в HashSet;
• много запросов: бинарный подъём даёт O(n log n) на подготовку и O(log n) на запрос, эйлеров обход с sparse table даёт O(1) на запрос, офлайн-алгоритм Тарьяна на DSU отвечает на пачку запросов почти за линейное время.

Для Java важна глубина: на вырожденном дереве в сотни тысяч узлов рекурсия упадёт с StackOverflowError, стек потока ограничен (-Xss). Надёжный вариант: итеративный обход с ArrayDeque, карта родителей HashMap<TreeNode, TreeNode> и подъём от p и q.

Где спотыкаются

Называют бинарный подъём решением за O(n). Это O(n log n) на подготовку, и выгоден он, только когда запросов много.

Сравнивают узлы по val, а не по ссылке. При повторяющихся значениях ответ получится неверным.

Не уточняют, гарантировано ли присутствие p и q в дереве. Классический алгоритм при отсутствии q вернёт p, и для честного ответа нужен флаг или счётчик найденных узлов.