Перестройте дерево из обходов до и после заказа

Question

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

например

данный предварительный заказ = ABCDEF
и почтовый заказ = BCEFDA

он должен построить дерево, эквивалентное
~~ ~~~~~
~ / ~ | ~ \ ~~~
В ~ С ~ Г ~~
~~~~ / ~ \ ~~
~~~ E ~~ F ~

(извините за тильду, это был единственный способ, которым я мог понять, как заставить дерево выглядеть правильно и все еще быть разборчивым)

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

PS Данное дерево может быть более или менее сложным с любым числом (предположительно <= 26) узлов

TL;DR
How do I use Pre-order and Post-order traversals to construct their original tree

Answer 1

Рекурсивное + итеративное решение

каждый уровень обрабатывает всю переданную ему строку

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

вызов с пустым часовым в качестве родителя A

Это даст вам результат в большинстве случаев.