树的恢复

ID: 1441

传统题

1000ms

128MiB

难度: (无)

上传者:

标签>

未分类

Description

Lucy最近正在学习数据结构中的二叉树(binary trees),为了更好学习二叉树的几种遍历,lucy常常自己随机写些二叉树。比如说下面这样的一棵二叉树。

D
        / \
       /   \
      B     E
     / \     \
    /   \     \
   A     C     G
              /
             /
            F

但是计算机是不能输入这样的图形的，只能用两组序列来保存二叉树：前序序列（节点访问顺序为:根，左节点，右节点），中序（节点访问顺序为:左节点，根，右节点），如上图，前序序列为DBACEGF 而中序序列为ABCDEFG.

这样的两组序列为重构这棵二叉树提供了足够的信息，然而做这样的工作是多么单调乏味，作为Lucy的好朋友，你就编个小程序来帮助她吧。

输入包含多个测试数据，每组测试数据提供一棵二叉树的前序遍历序列，中序遍历序列，每棵二叉树由26个大写字母组成且每个节点的字母不重复，所以两个遍历序列的长度都不超过26.测试数据一直输入到文件尾。

对于每组测试数据，请你输出后序序列（节点访问顺序为左节点，右节点，根）。

DBACEGF ABCDEFG
BCAD CBAD

ACBFGED
CDAB

未分类