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