이진 트리 복원

이진 트리의 여러 순회를 만들어 내는 것은 쉽지만, 이 문제는 그 반대를 요구한다. 이진 탐색 트리가 아닐 수도 있는 어떤 이진 트리의 전위 순회(pre-order)와 중위 순회(in-order)가 주어질 때, 원래 트리를 복원하고 그 트리의 후위 순회(post-order)를 출력하라. 단, 그러한 트리가 존재하는 경우에만 출력한다.

예를 들어, 아래 트리는 다음과 같은 순회 결과를 만든다.

            E
          /   \
        D       F
       /         \
      B           G
     / \           \
    A   C           I
                   / \
                  H   K
                     /
                    J

Preorder : EDBACFGIHKJ
Inorder  : ABCDEFGHIJK
Postorder: ACBDHJKIGFE

모든 노드의 문자가 서로 다르므로, 전위 순회와 중위 순회 한 쌍은 많아야 하나의 이진 트리를 결정한다.

입력은 여러 개의 트리로 이루어지며, 각 트리는 한 줄에 하나씩 주어진다. 마지막에는 # 한 글자만 있는 줄이 온다.

각 트리 줄에는 최대 26개의 서로 다른 대문자로 이루어진 두 문자열이 공백으로 구분되어 주어진다. 앞쪽이 전위 순회, 뒤쪽이 중위 순회이다.

<전위 순회> <중위 순회>

각 줄에서 두 문자열은 서로의 순열임이 보장된다.

각 트리에 대해, 복원한 트리의 후위 순회를 한 줄에 출력한다. 주어진 순회에 맞는 이진 트리가 없으면 대신 Invalid tree를 출력한다.