Tree Reorder

#描述#
Maybe you have taken the course called Data Structure
before. You should be familiar with the fact that no parenthesis is needed in
the suffix expression. But have you ever wondered why?<o:p>/o:p

We know that an expression can be uniquely represented
by a binary tree. The suffix expression is the post-order traversal of this
tree. Given the post-order traversal of a binary tree, each of whose non-leaf
nodes has exactly two children, we can reconstruct the original binary tree if
we are told which nodes in the post-order traversal are non-leaves. This means
that no parenthesis is needed in the suffix expression.<o:p>/o:p

Here is your task. Given a string S which represents
the post-order traversal of a binary tree T in which all of the non-leaf nodes
have exactly two children, and given which nodes in S are non-leaves, you must
reconstruct the binary tree and output the in-order traversal of T.<o:p>/o:p

Each node of T has a label, which is a letter(‘a’-‘z’, ‘A’-‘Z’). A lowercase letter(‘a’-’z’) means
the corresponding node is a leaf and an uppercase letter(‘A’-Z’) means the
corresponding node is a non-leaf.<o:p>/o:p

Notes<o:p>/o:p

<![if !supportLists]>l
<![endif]>The post-order traversal of a binary tree is to visit
the left subtree of the root first, then the right subtree and finally the
root.<o:p>/o:p

<![if !supportLists]>l
<![endif]>The in-order traversal of a binary tree is to visit
the left subtree of the root first, then the root, and finally the right
subtree.<o:p>/o:p

<![if !supportLists]>l
<![endif]>S contains letters(‘a’-‘z’,
‘A’-‘Z’) only and don’t contain any white spaces.<o:p>/o:p

<![if !supportLists]>l
<![endif]>The length of S is between 3 and 999, inclusive.<o:p>/o:p

<![if !supportLists]>l
<![endif]>The length of S is an odd number.<o:p>/o:p

<![if !supportLists]>l
<![endif]>S will be the post-order traversal of a binary tree.<o:p>/o:p

#格式#
##输入格式##
The input contains an integer on the first line, which indicates the number of test cases. Each test case contains one string S on a line, the post-order traversal of a binary tree.

##输出格式##
For each test case, output on a line one string which is the in-order traversal of the corresponding binary tree. There can be no white spaces in your output.

#样例1#
##样例输入1##

2
bcA
efBghCA

##样例输出1##

bAc
eBfAgCh

#限制#
1000ms
32768KB

#提示#

#来源#
lily

ID

1399

难度

分类

category1 点击显示

标签

tag1

递交数

已通过

通过率

上传者

chenbo

Tree Reorder

将题目复制到

Tree Reorder

信息

状态

开发

支持

Tree Reorder

将题目复制到

Tree Reorder

信息

状态

开发

支持

还没有账户？

登录