| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 134 | 38 | 32 | 39.506% |
It is very easy to produce the various traversals of a binary tree, however this problem requires you to produce the tree from the traversals. Specifically, given the pre-order and in-order traversals of a binary tree (not necessarily a binary search tree), reconstruct, if possible, the original tree.
For instance, the following tree will produce the traversals shown
E
/ \
D F
/ \
B G
/ \ \
A C I
/ \
H K
/
J
Preorder : EDBACFGIHKJ
Inorder : ABCDEFGHIJK
Postorder: ACBDHJKIGFE
Input will consist of representations of several trees, each on a single line, and terminated by a #. Each line will consist of two strings of up to 26 unique uppercase letters in the form
<pre-order> <space> <in-order>.
You can assume that the two strings will be permutations of each other.
Output will consist of the post-order traversal of the reconstructed tree if possible, otherwise the words 'Invalid tree'.
EDBACFGIHKJ ABCDEFGHIJK #
ACBDHJKIGFE
ICPC > Regionals > South Pacific > South Pacific Region > New Zealand Programming Contest > NZPC 2008 J번