Problem 21233 --普通数转二叉树

21233: 普通数转二叉树

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 65  Solved: 47
[Submit][Status][Web Board][Creator:][下载FPS1元][添加到购物车][下载测试数据1元][68kb]

Description

输入一棵普通有序树,输出该树的先根次序和后根次序。

Input

第一行为顶点个数n(1≤n≤26)。以下含n行,其中第i行(1≤i≤n)的元素依次为结点i的数据值ai(为一个小写字母)。以后各元素为结点i的儿子序列,以0结束。若ai后仅含一个0,则说明结点i为叶子。

Output

输出共两行,第一行该树的前序遍历,第二行为后续遍历,节点间没有空格

Sample Input

18
r 2 3 4 0
a 5 6 0
b 7 0
c 8 9 10 0
w 0
x 11 12 0
f 0
s 13 14 0
t 0
u 0
d 15 0
e 0
i 16 17 18 0
j 0
h 0
m 0
o 0
n 0

Sample Output

rawxdhebfcsimonjtu
hedxwfnomjiutscbar

HINT

Source

[Submit][Status]