Используйте обход дерева в порядке, чтобы определить, является ли BST или куча

Question

Учитывая эти прохождения в заказах:

1. 53, 1, 64, 23, 3, 29, 17, 2, 9, 19
2. 49, 32, 51, 71, 32, 10, 21, 8, 13, 11, 41, 17

Мне нужно определить, представляет ли каждый из этих списков действительными BST / Min или Max Heap или None.
Я пытался поступить, как приблизиться к этому, но помимо грузоподъемности каждый возможный вариант, я не мог понять «умный» способ решить это.

Какие индикаторы я могу использовать, если есть какие-либо, или путь, чтобы решить, что это будет буквально грубо принудительным для каждого варианта?

Answer 1

Ни один из них не может быть BST.Обход в заказах BST посещает вершины в неумеренном порядке их клавиш (это легко доказать по индукции).

Чтобы определить, являются ли они кучами, обратите внимание, что по количеству элементов в списке вы уже знаете топологию дерева (куча полностью двоичных деревьев до одномущеного уровня, и все листья наПоследний уровень упакован на левую сторону).Затем упражнения сводится к записи данных клавиш в том же порядке обхода и проверки, если свойство HeaP удерживает.

В конкретном примере первая последовательность не может быть обходом в порядке кучи, поскольку полученное дерево будет иметь путь с ключами 23, 1, 53 $ (в увеличении порядка глубины). Один и тот же аргумент применяется ко второй последовательности для пути с ключей 71 $, 32, 49 $ .