问题1412--Tree Recovery

1412: Tree Recovery

时间限制: 1 Sec  内存限制: 128 MB
提交: 23  解决: 16
[状态] [讨论版] [提交] [命题人:]
题目描述
Valentine非常喜欢玩二叉树,她喜欢的游戏是随意构造一棵二叉树,用大写字母编号标识结点。下图是她构造的二叉树中的一棵:

                                               D
                                              /   \
                                            B     E
                                          /   \      \
                                         A   C     G
                                                     /
                                                    F
    为了向她的后代记录她所创建的树,她给每棵树写下两串字符串:表示先根遍历(根,左子树,右子树)和中序遍历(左子树、根、右子树)的结果。
    对于上面的树,先根遍历的结果是DBACEGF ,中序遍历的结果是ABCDEFG
   
她认为这样一对字符串给出了足够的信息来重构这棵树(但她从未尝试过)。
    过了好些年,她认识到重构这些树的确是可能的,因为对于同一棵树,同一个字母不会用两次。
   
然而,如果手工重构这些树是非常乏味的,因此,请你编写一个程序来为她完成这一工作。
输入
输入包含一个或多个测试用例。每个测试用例一行,包含两个字符串,表示二叉树的先序遍历和中序遍历的结果。这两个字符串都是由大写字母组成的(因此它们的长度不超过26)。
输出
对于每个测试用例,转化为Valentine的二叉树,并在一行中输出树的后序遍历(左子树、右子树、根)的结果。
样例输入 Copy
DBACEGF ABCDEFG
BCAD CBAD
样例输出 Copy
ACBFGED
CDAB
来源/分类