У меня есть массив postorder размера дерева BST n, как мне показать, что из него можно построить только один BST. Я знаю, что могу перестроить дерево, если добавляю узлы справа налево, но как показать, что есть только одно правильное дерево?
Я пытался сказать, что есть два возможных дерева, и пытался показать, что это невозможно, но застрял
Это возможно только потому, что это BST. Напомним, что для того, чтобы двоичное дерево было действительным двоичным деревом поиска:
-Значения левых поддеревьев должны быть меньше значения корня
-Значения правых поддеревьев должны быть больше, чем значение корня
-Левые и правые поддеревья должны быть действительными деревьями двоичного поиска.
Поскольку мы знаем, что это должно быть так, мы можем восстановить дерево по списку элементов в пост-порядке. Последний элемент в массиве (позиция n) - это корень. Найдите самый правый элемент больше корня, и это первое правое поддерево корня. Найдите ближайший к концу массива элемент, который меньше корня, и это левый элемент. Рекурсивно примените это, чтобы получить дерево.
Пример:
[8,10,9,12,11]
11 <----root
9 - крайнее правое число меньше 11, поэтому это левое поддерево
11
/
/
9
а 12 - самый правый элемент больше 11, поэтому
11
/ \
/ \
9 12
Теперь наш корень равен 9, а крайнее правое число меньше 9 - 8, поэтому дерево становится
11
/ \
/ \
9 12
/ \
8
И следующее число больше 9 - 10, поэтому последнее дерево
11
/ \
/ \
9 12
/ \
8 10
Попробуйте убедить себя, что существуют и другие возможные допустимые деревья двоичного поиска с этими точками, но не, которые производят идентичный результат при обходе пост-заказа.
