5606. Ближайший общий предок
Medium
0 решили
Двоичное дерево задано списком в порядке уровней: у узла с индексом
Значения узлов уникальны. Даны два значения
i левый ребёнок — 2·i+1, правый — 2·i+2. Значение -1 означает, что узла нет. Корень — индекс 0.Значения узлов уникальны. Даны два значения
p и q, которые точно есть в дереве. Верните значение ближайшего общего предка.Примеры:
Вход:
tree = [3,5,1,6,2,0,8,-1,-1,7,4], p = 5, q = 1
Выход:
3
Объяснение: Корень — предок обоих.
Вход:
tree = [3,5,1,6,2,0,8,-1,-1,7,4], p = 5, q = 4
Выход:
5
Объяснение: 5 — предок 4.
Вход:
tree = [1, 2], p = 1, q = 2
Выход:
1
Объяснение: Корень.
Ограничения:
2 <= число узлов <= 2000, значения уникальны
Решите эту задачу в браузере
Создайте бесплатный аккаунт — редактор Python и Java, проверка на тестах за секунды.
Комментарии (0)
Зарегистрируйтесь или войдите, чтобы оставить комментарий
Пока нет комментариев. Будьте первым!