9063:复制二叉树

Time/Memory Limit:1000 MS/32768 K
Submitted: 790 Accepted: 512

 Problem Description

设有一棵二叉树,其节点值为字符型并假设各值互不相等,采用二叉链表存储表示。现输入其扩展二叉树的前序遍历序列,要求复制该二叉树,并对复制得来的二叉树进行中序遍历。

 Input

第一行为一个整数n,表示以下有n组测试数据,每组测试数据占一行,为扩展二叉树的前序遍历序列。

 Output

输出复制完的新二叉树的中序遍历序列,空二叉树则不输出任何信息。

 Sample Input

2
AB#D##C##
ABD##E##C#F##

 Sample Output

BDAC
DBEACF

 Author

wj

 Recommend

zh