遍历问题

(时间限制为：1000毫秒)





描述：

已知二叉树的中序和先序遍历可以唯一确定后序遍历、已知中序和后序遍历可以唯一确定先序遍历，但已知先序和后序，却不一定能唯一确定中序遍历。现要求根据输入的中序遍历结果及某一种遍历，要求输出另一种遍历。

输入：

输入包括若干个测试用例，第一行为一个自然数n，表示用例个数，接下来4n行，即每个用例占4行，其中第一行表示第一种遍历方式，第二行为第一种遍历结果，第三行为第二种遍历方式，第4行为第二种遍历结果。注明：先序遍历方式用“pre”表示，中序遍历方式用“in”表示，后序遍历方式用“post”表示。

输出：

对每个测试用例，输出相应的另一种遍历方式及结果。每个用例用一行输出，输出格式为先输出相应的遍历方式，然后一个冒号，再加一个空格，最后输出相应的遍历结果。

样例输入：

1

pre

ABDFCEG

in

BFDAEGC



样例输出：

post: FDBGECA



-Traversal problem



(Time limit: 1000 ms)











Descr iption:



Known binary tree in preorder traversal sequence and uniquely determine the order of traversal, the known sequence and can be uniquely determined after traversing the first order traversal, it is known that the first order and the order, not necessarily the only determine the order of a traversal. Are required in accordance with the input sequence results and a certain traversal traversal traversal required a different output.



Input:



The input includes a number of test cases, the first act of a natural number n, that the number of use cases, followed by 4n lines, each use case, 4 lines, which traverse the first line means that the first and second acts of the first traversal results , the third act the second traversal methods, 4 the second traversal behavior results. State: first traversing way with "pre" said traversal methods in order to use "in" that way, after traversing with the "post", said.



Output: