Problem 1452 --转换二叉树

1452: 转换二叉树

"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $172$ 正确数量 $152$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签 数据结构 STL 字符串
DJ非常痴迷于数据结构,二叉树是他最喜欢的结构模型。这种每个顶点的度不大于2的简单的图总是能激发他的灵感。然而,二叉树的表示方法是一个困扰他已久的问题。如果用链表表示,不直观;画成图形,计算机又难以存储。好在他现在发现了一种既直观,计算机又便于存储的表示方法。该方法定义如下:

1、如果二叉树中节点X是叶子节点,则该节点直接表示为X。
2、如果二叉树中节点X有左子树,则该节点表示为(...)X,括号内为X的左子树。
3、如果二叉树中节点X有右子树,则该节点表示为X(...),括号内为X的右子树。
4、如果二叉树中节点X有左右子树,则该节点表示为(...)X(...),左边括号内为左子树,右边括号内为右子树。

现在DJ有许多二叉树的先序序列和中序序列,DJ要你写个程序帮他把这些二叉树转换为上述表示方法。

输入第一行为一个整数N,表示有N个待转换的二叉树。

接下来有N行,每行由两个字符串组成,中间用空格分开。
每行的第一个字符串为二叉树的先序序列,第二个字符串为二叉树的中序序列。
输入字符串由大写字母组成,每个字母代表二叉树的一个节点,不会有两个相同的字母。
你可以假设不会输入无效数据。

每组数据输出占一行,输出转换后的二叉树。
2
AB AB
ABCD BCAD
A(B)
(B(C))A(D)

推荐代码 查看1452 所有题解 上传题解视频得图灵币

本题记录 用 户(点击查看用户) 运行号(点击购买题解) 时 间
算法最快[$0 $ms] 敢敢的心心 825946 2022-03-23 10:25:03
内存最少[$948 $KB] 未实名用户 85759 2017-05-04 19:08:55
第一AC 赵佳强@计算机科学与技术152 84005 2017-04-25 21:46:45
第一挑战 赵佳强@计算机科学与技术152 84005 2017-04-25 21:46:45

赛题来源/所属竞赛 Anhui Programming Contest 2011 N/A

竞赛编号 竞赛名称 竞赛时间 访问比赛
1683 2021-2022-2学期<算法分析与设计> 第4周练习:数据结构应用 2022-03-14 13:00:00 请登录
1645 安科ACM集训队-2021(1)数据结构字符串,基础数据结构专题 2021-05-01 10:00:00 请登录
1345 ACM中级算法:STL算法、基础数据结构 2019-05-13 16:00:00 请登录
1332 图灵2019五一高级算法集训营:数据结构字符串、基础数据结构、专题 2019-05-02 09:00:00 请登录
1074 2011安徽省ACM程序设计大赛 2017-04-25 09:00:00 请登录