Skip to content

1135: 叮铃铃!

题目

题目描述

“叮铃铃~”风吹过风铃发出清脆悦耳的声音,宛若一首欢快动听的歌。

常音最喜欢风铃的声音,Anoxiacxy便亲手编了好多好多串送给常音。常音说她最喜欢五颜六色的风铃,“这样才显得不单调嘛!”因此Anoxiacxy对每串风铃的每颗铃铛,都精心选用了不同颜色、不同材质的。他还坚持在一颗铃铛下最多只挂两颗铃铛,并这样对常音解释道:“当你拎起这串风铃,铃铛整整齐齐地垂下来倾泻在一个平面上,就像……”

“一棵二叉树!多漂亮!”(逃)

每天早晨,常音伴着阳台上风铃的声音起来,迎接新的一天;每天夜晚,常音关上阳台门,安然进入梦想。她也坚持每天向Anoxiacxy道早安晚安时各给他发一张风铃的照片,晚上的时候还会问他晚上挂在阳台上的和早上的是不是同一串。有时,常音是会在晚上换一串新的风铃挂出去的;而更多的时候,她没有换风铃,只是挑一些系在同一颗铃铛下的两颗铃铛疯狂互换。

Anoxiacxy被常音的障眼法搞得晕头转向。他用一杯奶茶和你做了一笔交易:接下来的一个星期,他会把每天早晚的两张照片发给你,你来帮他判断判断,这早晚照片里的两串风铃是同一串吗?

给定两张照片中的风铃 T1 和 T2。如果 T1 可以通过若干次左右孩子互换就变成 T2 ,则我们称两串是“同构”的。

例如图1给出的两串就是同构的,因为我们把其中一串的结点A、B、G的左右孩子互换后,就得到另外一串。而图2就不是同构的。

现给定两串风铃,请你判断它们是否是同构的。

输入格式

输入给出两棵二叉树树的信息。对于每棵树,首先在一行中给出一个非负整数 $N$,即该树的结点数(此时假设结点从 $0$ 到 $N−1$ 编号);随后 $N$ 行,第 $i$ 行对应编号第 $i$ 个结点,给出该结点中存储的 $1$ 个英文大写字母、其左孩子结点的编号、右孩子结点的编号。如果孩子结点为空,则在相应位置上给出 -。给出的数据间用一个空格分隔。注意:题目保证每个结点中存储的字母是不同的。

输出格式

如果两棵树是同构的,输出 Yes,否则输出 No

样例输入

text 8 A 1 2 B 3 4 C 5 - D - - E 6 - G 7 - F - - H - - 8 G - 4 B 7 6 F - - A 5 1 H - - C 0 - D - - E 2 -

样例输入2

text 8 B 5 7 F - - A 0 3 C 6 - H - - D - - G 4 - E 1 - 8 D 6 - B 5 - E - - H - - C 0 2 G - 3 F - - A 1 4

样例输出

样例输出1

text Yes //就是上图图1

样例输出2

text No

数据范围

对于 50 % 的数据,保证 $1 \leq N \leq 10$

对于 100 % 的数据,保证 $1 \leq N \leq 26$

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!