#jag2016secretspringc. [jag2016secretspring_c]みさわさんの根付き木
[jag2016secretspring_c]みさわさんの根付き木
问题陈述
你意识到你的好朋友Misawa的生日快到了,决定送他一棵根二叉树作为礼物。 在这里,根二叉树是以下图形结构。
- 每个顶点正好有一个称为其父节点的顶点,并且与父节点相连。但是,只有称为根的一个顶点例外,它没有父节点。
- 每个顶点正好有一个称为其左子节点的顶点,或者没有左子节点。如果有左子节点,则左子节点与顶点相连,其父节点是该顶点。
- 每个顶点正好有一个称为其右子节点的顶点,或者没有右子节点。如果有右子节点,则右子节点与顶点相连,其父节点是该顶点。
图1. 两个根二叉树及其组合示例
由于你想要送出手工制作的物品,所以决定购买两棵商业根二叉树,并将它们叠加在一起合成一棵更好的根二叉树。每个购买的树上的每个节点都标有非负整数。Misawa喜欢节点数量少但数值较大的树,因此按照以下步骤创建新的二叉树。
- 将两个树的根上的整数相加,将结果作为新树的根上的整数。
- 如果两个树的根都有左子节点,请创建一个合并的二叉树,其根为这些根,并将其设置为新树的左子节点。否则,新树的根没有左子节点。
- 如果两个树的根都有右子节点,请创建一个合并的二叉树,其根为这些根,并将其设置为新树的右子节点。否则,新树的根没有右子节点。
你决定在进行实际合成之前,先让自己确认最终生成的根二叉树会是什么样子。给出两棵购买的根二叉树的信息,按照上述步骤创建合成后的新根二叉树。
在这里,根二叉树的信息将被表示为以下形式的字符串。
(表示左子节点的字符串)[根上的整数](表示右子节点的字符串)
空树将表示为空字符串。例如,图1的合成的新根二叉树将表示为(()[6]())[8](((()[4]())[7]())[9]())
。
输入
输入将遵循以下格式。
其中和分别表示购买的两棵根二叉树的信息,它们的长度为7到1000个字符之间。给定的信息将遵循前面讨论过的格式,并且不包含任何额外的空格字符等。不会输入不存在节点的根二叉树。可以假设每个节点上写的整数在0到1000之间。然而,注意输出中的每个节点上写的整数可能不在这个范围内。
输出
以一行形式输出两棵根二叉树合并后形成的新根二叉树的信息。特别地,注意不要包含行末的换行符和额外的空白字符。