Task 80. Двоичное дерево поиска
UniLecsЗадача: вам дан массив неповторяющихся чисел. Необходимо определить, существует ли такое двоичное дерево поиска, в ктр эта последовательность является путем от корня к какому либо листу.
Входные данные: arr - массив неповторящихся чисел, размер массива от 1 до 10000. Значения массива - любые целые числа.
Вывод: true - если дерево, соответствующее заданному пути, существует. Иначе false.
Пример:
- arr = [8, 3, 6, 4]
Answer = True
- arr = [8, 4, 6, 3]
Answer = False
Идея: для начала приведем определение двоичного дерева поиска.
Двоичное дерево поиска - это двоичное дерево, для которого выполняются следующие дополнительные условия (свойства дерева поиска):
- Оба поддерева — левое и правое — являются двоичными деревьями поиска.
- У всех узлов левого поддерева произвольного узла X значения ключей данных меньше, нежели значение ключа данных самого узла X.
- У всех узлов правого поддерева произвольного узла X значения ключей данных больше либо равны, нежели значение ключа данных самого узла X.
Перейдем к разбору решения: рассмотрим два последовательных числа входного массива: previous(prev) и current (cur).
Если cur > prev, то далее числа должны лежать в интервале [prev; IntMax]. Иначе следующие числа должны принадлежать интервалу [IntMin, prev]. Эти выводы мы делаем исходя из определения двоичного дерева поиска.
Если на какой либо итерации значение cur не принадлежит текущему интервалу, то такого пути в дереве не существует.
Реализация:
https://gist.github.com/unilecs/8f36841b61aa1c202430689b2b59b725
Тест: