# Tree

## Tree

Little Valentine liked playing with binary trees very much. Her favorite game was constructing randomly looking binary trees with capital letters in the nodes.  This is an example of one of her creations:

```                                                D

/ \

/   \

B     E

/ \     \

/   \     \

A     C     G

/

/

F```

To record her trees for future generations, she wrote down two strings for each tree: a preorder traversal (root, left subtree, right subtree) and an inorder traversal (left subtree, root, right subtree). For the tree drawn above the preorder traversal is DBACEGF and the inorder traversal is ABCDEFG.  She thought that such a pair of strings would give enough information to reconstruct the tree later (but she never tried it).  Now, years later, looking again at the strings, she realized that reconstructing the trees was indeed possible, but only because she never had used the same letter twice in the same tree.  However, doing the reconstruction by hand, soon turned out to be tedious.  So now she asks you to write a program that does the job for her!

```DBACEGF ABCDEFG
BCAD CBAD```

```ACBFGED
CDAB```
```
#include <iostream>
#include <string>

using namespace std;
string pos;
void convert(string pre,string in)
{

if(in.size()==1)
pos+=in;
else
{
int k=in.find(pre.substr(0,1));

if(k>0)
convert(pre.substr(1,k),in.substr(0,k));
if(k<in.size()-1)
convert(pre.substr(k+1,pre.size()-k-1),in.substr(k+1,in.size()-k-1));

pos+=in[k];
}

}

int main()
{
string str_pre;
string str_in;

while(cin>>str_pre>>str_in && !cin.eof())
{

convert(str_pre,str_in);

cout<<pos<<endl;
pos = "\0";

}

return 0;
}        ```

0 条评论

• ### python如何以表格形式打印输出

虽说可以用 prettytable 实现这个效果，不过还得安装这个库，需求比较简单就不考虑安装第三方依赖了，所以得自己写

• ### JS 中对象的简单创建和继承

比如 var obj = new Object(); // 相当于var obj = {};

• ### 对称排序

In your job at Albatross Circus Management (yes, it's run by a bunch of clowns),...

• ### C# 从1到Core--委托与事件

委托与事件在C#1.0的时候就有了，随着C#版本的不断更新，有些写法和功能也在不断改变。本文温故一下这些改变，以及在NET Core中关于事件的一点改变。

• ### 云基础虚拟网络的有效欺骗网络体系（CS CR）

云基础虚拟网络在安全性方面的问题日益凸显出来，特别是对于中小企业运营的云虚拟网络，网络安全问题更加严峻。新兴的欺骗系统为解决云基础虚拟网络的安全问题带来了希望。...

• ### SAP HANA里的中文排序问题

版权声明：本文为博主原创文章，遵循 CC 4.0 by-sa 版权协议，转载请附上原文出处链接和本声明。

• ### 萨提亚·纳德拉与沈向洋CVPR对谈：那些未来可期的计算机视觉研究与应用

编者按：6月16日，CVPR 2020 大会以全球连线的形式如期开幕。在大会的首场主题演讲中，微软公司 CEO 萨提亚·纳德拉与微软公司前执行副总裁沈向洋进行了...

• ### 萨提亚·纳德拉、沈向洋CVPR对谈：那些未来可期的计算机视觉研究与应用

6月16日，CVPR 2020 大会以全球连线的形式如期开幕。在大会的首场主题演讲中，微软公司 CEO 萨提亚·纳德拉与微软公司前执行副总裁沈向洋进行了一场精彩...