新二叉树（前序遍历）

题目概述

给定一棵二叉树的描述，请输出它的前序遍历结果。

• 节点用大写或小写英文字母表示（本题数据规模通常用小写字母）。
• 空子节点用 * 表示。
• 保证输入的第一行节点（在后续 n 行中的第一行）所表示的节点就是根节点。

输入格式

• 第 1 行：整数 n（节点数），\(1 \le n \le 26\)。

• 第 2 ~ n+1 行：每行 3 个字符，形如 xyz：

  • x 表示当前节点；
  • y 表示 x 的左孩子，若无则为 *；
  • z 表示 x 的右孩子，若无则为 *。

注：每个出现过的非 * 字母恰好对应一个节点描述行；不存在环；第一行出现的节点即为根。

输出格式

输出该二叉树的前序遍历序列（不含空格与换行，仅输出字母节点）。

前序遍历顺序：根 → 左子树 → 右子树

样例

输入

6
abc
bdi
cj*
d**
i**
j**

输出

abdicj

说明

• a 的左、右孩子分别为 b、c；
• b 的左、右孩子分别为 d、i；
• c 的左孩子为 j、右孩子为空 *；
• d、i、j 均为叶子（左右孩子均为 *）。 按前序遍历依次访问得到 a b d i c j，输出为 abdicj。