Премиум

#93 Ближайший общий предок в бинарном дереве

Компании:
Яндекс
Темы:
АлгоритмыДеревьяПрактика

Дан класс, представляющий узел бинарного дерева:

public class TreeNode {
    TreeNode parent;
    TreeNode left;
    TreeNode right;
}

Необходимо реализовать метод getLowestCommonParent(TreeNode first, TreeNode second), который находит ближайшего общего предка (LCA) для двух заданных узлов в бинарном дереве.

Метод должен работать с ограничением по памяти O(1), то есть нельзя использовать дополнительные структуры данных, такие как коллекции, массивы и т.д.

Разбор вопроса

Ментор
Ответь как на реальном собеседовании. Я задам уточняющие вопросы, а затем сравню твой ответ с эталонным и покажу точность в %.
Войди, чтобы начать диалог Ментор ведёт диалог по текущему вопросу и учитывает предыдущие сообщения.
Войти