Восстановление бинарного дерева

Приведу ответ с одного сайта:

Если одним префиксным/инфиксным/постфиксным — то, разумеется, нет. А если двумя — дело уже интереснее (при условии, разумеется, что все узлы разные). Ну, например, как восстановить дерево, которое было пройдено сначала префиксно, потом постфиксно (самый сложный и интересный случай). Признаюсь сразу: полное восстановление невозможно, ведь ситуации «без левых сыновей» и «без правых сыновей» различить нельзя.

Если длины не совпадают, СТОП: некорректные данные.
В префиксном обходе корень в начале, в постфиксном — в конце. Если они не одинаковы, СТОП: некорректные данные.
Если в обходе один элемент — с этим всё понятно.
Второй элемент префиксного обхода — левый сын. Ищем его в постфиксном обходе. Если он предпоследний — перед нами та самая ситуация «у дерева один сын», и рекурсивно запускаем алгоритм на обходах без корня. В противном случае выкусываем подстроки нужной длины (реально или виртуально), дважды запускаем алгоритм рекурсивно.

Пример: у нас дерево.
a
/\
b c
/\ /
d e f
Префиксный обход abdecf, постфиксный debfca. Корень a, левый сын b, он в постфиксном обходе на третьей позиции. Рекурсивно запускаем алгоритм на парах bde/deb и cf/fc.

Можно решать рекурсивно, для случая In+Post передавая аргументы InLeft, InRight, PostRoot

Обработать случаи InLeft>InRight (обрыв рекурсии) и InLeft=InRight - вывод листового элемента.

Найти в In элемент In[RootIndex] = Post[PostRoot] и вывести узловой элемент In[RootIndex] Запустить рекурсию для его поддеревьев в диапазонах левее и правее RootIndex, с использованием корней поддеревьевPostRoot-1 и PostRoot-RootIndex

Для случая In+Pre всё будет похоже, за исключением корня слева и подкорней правее