5817. k-й элемент дерева поиска
Medium
0 решили
Дерево поиска задано списком в порядке уровней: у узла с индексом
Для каждого узла все значения слева строго меньше его, все справа — строго больше. Значения не повторяются.
i левый ребёнок — 2·i+1, правый — 2·i+2. Значение -1 означает, что узла нет. Корень — индекс 0. Если в слоте -1, его потомки в дерево не входят.Для каждого узла все значения слева строго меньше его, все справа — строго больше. Значения не повторяются.
k считается с единицы. Верните k-й по возрастанию элемент. Он есть: k не больше числа узлов.Примеры:
Вход:
tree = [5, 3, 6, 2, 4, -1, -1, 1], k = 3
Выход:
3
Объяснение: По возрастанию значения идут 1, 2, 3, 4, 5, 6. Третье — 3.
Вход:
tree = [2, 1, 3], k = 1
Выход:
1
Объяснение: Самое маленькое лежит в левом листе.
Вход:
tree = [4, 2, 6, 1, 3, 5, 7], k = 4
Выход:
4
Объяснение: Середина ряда 1…7. Четвёртый элемент — корень 4.
Ограничения:
0 <= tree.length <= 10^4
1 <= k <= число узлов
дерево — дерево поиска, значения уникальны
значение узла от -10^9 до 10^9 и не равно -1
-1 означает отсутствие узла
Решите эту задачу в браузере
Создайте бесплатный аккаунт — редактор Python и Java, проверка на тестах за секунды.
Комментарии (0)
Зарегистрируйтесь или войдите, чтобы оставить комментарий
Пока нет комментариев. Будьте первым!