Контест Senior Деревья обновлено
Может ли последовательность быть прямым обходом BST
Условие
Дана последовательность из n различных чисел. Проверьте, может ли она быть результатом прямого обхода (preorder: корень, левое поддерево, правое поддерево) некоторого двоичного дерева поиска. В дереве поиска все ключи левого поддерева меньше ключа вершины, правого больше.
Ввод: в первой строке n (1 ≤ n ≤ 2500), во второй n различных чисел от 1 до 10⁹.
Вывод: YES или NO.
Пример 1
Ввод:
5
5 2 1 3 6
Вывод:
YES
Пример 2
Ввод:
3
2 3 1
Вывод:
NO
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.