Рассмотрим ситуацию, когда у вас есть два списка узлов, из которых все, что вам известно, это то, что один является представлением обхода по предварительному заказу некоторого дерева, а другой - представлением обхода по предварительному заказу того же дерева.

Я считаю, что можно восстановить дерево именно из этих двух списков, и я думаю, что у меня есть алгоритм для этого, но я не доказал это. Поскольку это будет частью магистерского проекта, я должен быть абсолютно уверен, что это возможно и правильно (математически доказано). Однако он не будет в центре внимания проекта, поэтому мне было интересно, есть ли какой-нибудь источник (то есть бумага или книга), который я мог бы привести в качестве доказательства. (Может быть, в TAOCP? Кто-нибудь знает раздел возможно?)

Короче говоря, мне нужен проверенный алгоритм в цитируемом ресурсе, который восстанавливает дерево по его обходам до и после заказа.

Примечание: рассматриваемое дерево, вероятно, не будет двоичным, или сбалансированным, или чем-то, что сделало бы его слишком простым.

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

Примечание 3: узел может иметь любое количество дочерних элементов.

Примечание 4: Я забочусь только о порядке братьев и сестер. Левый или правый не имеет значения, когда есть только один ребенок.