LG#P1305. 新二叉树
新二叉树
题目描述
给定一棵有 个节点的二叉树,每个节点用一个互不相同的小写字母表示。每个节点至多有一个左子节点和一个右子节点。输入第一条节点记录中的节点是根节点。
请输出这棵树的前序遍历。前序遍历的顺序是:先访问当前节点,再前序遍历左子树,最后前序遍历右子树;空子树不输出任何字符。
输入格式
第一行输入一个整数 ,代表节点数量。
此后 行,每行输入一个长度为 的字符串。第一个字符为当前节点,第二、三个字符分别为它的左、右子节点。节点字符均为小写字母,字符 表示对应子节点不存在。
保证这些记录恰好构成一棵二叉树,第一条记录对应根节点,其余记录的顺序不作要求。
输出格式
输出一行字符串,代表前序遍历中依次访问的节点字母,中间不加空格。
测试样例
6
abc
bdi
cj*
d**
i**
j**
abdicj
样例 1 解释
先访问根节点 ,然后依次访问左子树中的 ,最后访问右子树中的 ,得到 。
3
z*a
a*b
b**
zab