Как привести два узла дерева к одному уровню для поиска наименьшего общего предка

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

Знаете ли вы вариант LCA для дерева со ссылками на родителя, где рекурсия от корня не нужна. Ключевые слова в вопросе «к одному уровню»: интервьюер ждёт подсчёт глубины и подъём, а не классический рекурсивный обход. Следом спрашивают, что делать, если запросов миллион.

Как отвечать

Сначала уточните, есть ли у узла поле parent. Если есть, алгоритм такой:

int depth(Node n) { int d = 0; while (n.parent != null) { n = n.parent; d++; } return d; }

Node lca(Node a, Node b) {
    int da = depth(a), db = depth(b);
    while (da > db) { a = a.parent; da--; }
    while (db > da) { b = b.parent; db--; }
    while (a != b) { a = a.parent; b = b.parent; }
    return a;
}

Объясните, почему это работает: после выравнивания оба указателя стоят на одной глубине, до общего предка им идти одинаковое число шагов, и встречаются они ровно в нём. Время O(h), где h высота дерева, память O(1). На вырожденном дереве h равно n.

Полезные дополнения:

• без подсчёта глубины: приём из задачи о пересечении двух связных списков. Два указателя идут вверх, дойдя до корня, каждый перескакивает на стартовый узел другого. Суммарный путь одинаков, и встречаются они в LCA;
• много запросов: двоичный подъём. Для каждого узла заранее считаются предки на 1, 2, 4, 8 уровней выше, это O(n log n) времени и памяти, после чего выравнивание и поиск идут прыжками за O(log n);
• нет ссылки на родителя: либо рекурсивный обход от корня за O(n), либо сохранить пути от корня до обоих узлов и найти последний общий элемент.

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

Отвечают рекурсией от корня, не услышав вопрос. Решение верное, но про выравнивание уровней в нём ничего нет, и интервьюер это заметит.

Сравнивают узлы по значению a.val == b.val вместо ссылок. В дереве с повторяющимися значениями алгоритм остановится не там.

Забывают случай, когда один узел сам предок другого. Этот код с ним справляется, но при решении с нуля его часто теряют, поэтому проговорите его вслух.