Одной из широко известных структур данных для представления множеств является двоичное дерево поиска. Каждый узел v такого дерева содержит один элемент множества, при этом все элементы в левом поддереве v должны быть меньше элемента в v, а элементы в правом поддереве v должны быть больше элемента в v. Пример двоичного дерева поиска показан на рисунке. Узел называется корнем, если у него нет родителя (узел 5 на рисунке). Узел называется листом, если у него нет детей (узлы 2, 4 и 8 на рисунке). Путём в дереве назовём последовательность номеров узлов, таких что каждый следующий узел является непосредственным потомком предыдущего.
Вам дана последовательность неповторяющихся целых чисел. Требуется определить, существует ли такое двоичное дерево поиска, в котором эта последовательность является путём от корня к какому-то листу. Например, дерево поиска с путём 5-1-3-2 существует, а с путём 5-2-3-1 нет.
Задано последовательность чисел, разделённых пробелами и/или переводами строк. До первого и после последнего числа могут быть пробелы и переводы строк. Все числа различны. Количество чисел от 1 до 50 000. Значения чисел от -2 147 483 648 до 2 147 483 647включительно.
Выведите слово "YES", если дерево, соответствующее заданному пути, существует, и "NO" в противном случае.
#include <iostream>
#include <algorithm>
using namespace std;
int MAX = 2147483647;
int MIN = -2147483648;
int main() {
int prev, cur;
scanf("%d", &prev);
while (scanf("%d", &cur) == 1)
{
//Если значение cur не принадлежит интервалу[min; max], то искомого пути в дереве не существует.
if (cur < MIN || cur > MAX)
{
puts("NO");
return 0;
}
//Изменяем границы интервала[min; max].
if (cur > prev) MIN = prev;
else MAX = prev;
prev = cur;
}
//Если все числа обработаны корректно, то искомый путь в дереве существует.
puts("YES");
return 0;
}
Есть решение которого нет на сайте? Пиши admin@devexe.top