SeniorКодИногдаЕщё не отвечали
Наименьший общий предок в дереве с parent-указателями, O(1) памяти
У каждой вершины есть parent, left, right. Дерево НЕ является деревом поиска. Верните наименьшего общего предка двух заданных вершин, используя O(1) доп. памяти.
Требования:
- O(h) по времени, где
h— высота дерева; O(1) доп. памяти (без множеств и стека рекурсии).
struct Node { Node* parent; Node* left; Node* right; };
Node* lca(Node* a, Node* b) {
// ваш код здесь
}Допишите реализацию.
Вычислите глубину каждой вершины подъёмом по parent к корню. Поднимите более глубокую вершину на разность глубин, чтобы обе были на одном уровне, затем двигайте обе вверх синхронно до встречи указателей — эта вершина и есть LCA. O(h) время, O(1) память.
- ✗Использовать хеш-множество предков, нарушая требование O(1) памяти
- ✗Предполагать дерево поиска и сравнивать значения, что не работает на общем дереве
- ✗Забыть выровнять глубины перед синхронным подъёмом
- →Как вычислить глубины без дополнительного хранилища?
- →Каков вариант за O(d) с экспоненциальными шагами вверх?
Оглавление
Задача
Найдите LCA двух вершин дерева с parent-указателями за O(h) времени и O(1) памяти.
Решение
struct Node { Node* parent; Node* left; Node* right; };
static int depth(Node* n) { int d = 0; for (; n; 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; // встреча = LCA
}Ключевые моменты
- Считаем глубины подъёмом по
parent, без доп. памяти. - Выравниваем глубины, затем поднимаемся синхронно до встречи.
- O(h) времени, O(1) памяти — отличает от рекурсивного и от множества предков.
Оглавление
