Войти Регистрация
Алгоритмы

168. Правильное ли дерево поиска

Средняя

Дерево задано списком nodes: nodes[i] = [value, left, right], где left и right — индексы детей или -1. Корень — узел 0, пустой список — пустое дерево.

Верните True, если для каждого узла все значения в левом поддереве строго меньше его значения, а в правом — строго больше. Иначе False.

В работе: Индекс по id сообщений в виде дерева: если порядок нарушен в одном узле, поиск начнёт пропускать сообщения.

Пример 1

Ввод
nodes = [[8, 1, 2], [3, -1, -1], [10, -1, -1]]
Вывод
True

3 < 8 < 10.

Пример 2

Ввод
nodes = [[8, 1, 2], [3, -1, 3], [10, -1, -1], [9, -1, -1]]
Вывод
False

9 — правый ребёнок 3, но лежит в левом поддереве 8. Проверка только детей этого не увидит.

Ограничения

  • 0 ≤ длина nodes ≤ 10⁵
  • Глубина дерева может достигать 10⁵
  • |value| ≤ 10⁹
  • Лимит — 2 с на тест (1500 мс).
Как вызывается ваш код Читать ввод и печатать ответ не нужно: мы вызываем функцию на каждом тесте и сравниваем то, что она вернула. print() и console.log() уходят в консоль. 
def is_search_tree(nodes):
ДеревьяДвоичное дерево поискаОбход в глубинуцельO(n)

Источник: VK, фронтенд, репозиторий кандидата на GitHub. Условие пересказано своими словами.