← К задачам Режим собеседования 30:00
Обычный режим К собеседованию ← Предыдущая Следующая →

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 означает отсутствие узла

Теги:

Часто на собесе Деревья

Комментарии (0)

Зарегистрируйтесь или войдите, чтобы оставить комментарий

Пока нет комментариев. Будьте первым!