Сколько путешествий по дереву нужно, чтобы восстановить двоичное дерево?

Question

Сколько обходов деревьев (предварительный порядок, порядок, почтовый порядок) мне нужно, по крайней мере, для восстановления двоичного дерева.Я почти уверен, что это два, но у меня есть проблемы с объяснением почему.Я также сказал бы, что реконструкция возможна с каждой комбинацией этих трех типов.

Было бы замечательно, если бы кто-то мог дать мне правильное объяснение;).

Answer 1

Если у вас есть только один обход (например, inorder), вы не можете восстановить уникальное дерево.Вы можете объяснить это, приведя пример.

Предположим, что обход дерева по порядку: ABC.Тогда может быть много деревьев, которые можно восстановить из этого:

A               B                C
 \             /  \             /
  B           A    C           B
   \                          /
    C                        A

Следовательно, вам нужно 2 обхода для уникальной реконструкции дерева уникально .