Выбор ответа Middle Деревья обновлено
Общий предок в BST
Вопрос
Нужно найти наименьшего общего предка узлов p и q в BST. Какой подход самый простой и быстрый?
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: Спуск от корня: оба меньше, влево; оба больше, вправо. Свойство BST говорит, где лежат p и q.
Варианты ответа
- Найти пути от корня до p и до q и сравнить их до расхождения
- BFS по всему дереву с запоминанием родителя каждого узла
- Сортировка значений и выбор медианы между p и q
- Спуск от корня: оба меньше, влево; оба больше, вправоправильный ответ
Разбор
Свойство BST говорит, где лежат p и q. Узел, на котором они «расходятся» (или один из них сам узел), и есть LCA. O(h) времени, O(1) памяти в итеративном варианте.
- Пути тоже работают, но тратят O(h) памяти и два прохода; это решение для обычного дерева.
- BFS O(n) не использует свойство BST.
- Сортировка теряет структуру дерева.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.