9069:交换左右子树

Time/Memory Limit:1000 MS/32768 K
Submitted: 760 Accepted: 453

 Problem Description

设有一棵二叉树,其节点值为字符型并假设各值互不相等,采用二叉链表存储表示。现输入其扩展二叉树的前序遍历序列,要求编写一个算法交换二叉树中所有节点的左右子树,并输出交换后的前序遍历。

 Input

输入的第一行为一个整数n,表示接下来有n组数据。
接下来n组,每组占一行,每行包含一个扩展二叉树的前序遍历

 Output

对于每组数据,若二叉树不为空,输出交换完左右子树后的前序遍历,每组输出占一行;否则,不输出任何信息。

 Sample Input

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

 Sample Output

ACBD
ACFBED

 Author

hsq

 Recommend

zh