程序设计在线评测(Online Judge)

从http://acm.hnust.edu.cn/web登录可查看比赛的OI排名分。

问题 1070. -- 二叉树遍历

1070: 二叉树遍历

时间限制: 1 Sec  内存限制: 128 MB
提交: 1107  解决: 489
[提交][状态][讨论版]

题目描述

对于二叉树T,可以有先序遍历、中序遍历和后序遍历三种遍历方式。现在我们要求给出一棵二叉树的先序遍历序列和中序遍历序列,输出它的广度优先遍历序列。 

输入

第一行为一个整数t(0<t<10),表示测试用例个数。 以下t行,每行输入一个测试用例,包含两个字符序列s1和s2,其中s1为一棵二叉树的先序遍历序列,s2为中序遍历序列。s1和s2之间用一个空格分 隔。序列只包含大写字母,并且每个字母最多只会出现一次。

输出

为每个测试用例单独一行输出广度优先遍历序列。

样例输入

2
DBACEGF ABCDEFG
BCAD CBAD

样例输出

DBEACGF
BCAD

提示

本题主要测试对二叉树遍历的理解。需要先根据先序序列和中序序列建立二叉树,然后对二叉树进行按层次的遍历。

来源

[提交][状态][讨论版]