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! 

输入The input will contain one or more test cases.  Each test case consists of one line containing two strings preord and inord, representing the preorder traversal and inorder traversal of a binary tree. Both strings consist of unique capital letters. (Thus they are not longer than 26 characters.)  Input is terminated by end of file.输出For each test case, recover Valentine's binary tree and print one line containing the tree's postorder traversal (left subtree, right subtree, root).样例输入

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 条评论
登录 后参与评论

相关文章

来自专栏小樱的经验随笔

Code forces 719A Vitya in the Countryside

A. Vitya in the Countryside time limit per test:1 second memory limit per test:2...

3436
来自专栏小樱的经验随笔

Gym 100952D&&2015 HIAST Collegiate Programming Contest D. Time to go back【杨辉三角预处理,组合数,dp】

D. Time to go back time limit per test:1 second memory limit per test:256 megaby...

2876
来自专栏数据结构与算法

POJ 1985 Cow Marathon(树的直径)

Description After hearing about the epidemic of obesity in the USA, Farmer John...

3436
来自专栏mukekeheart的iOS之旅

No.009 Palindrome Number

9. Palindrome Number Total Accepted: 136330 Total Submissions: 418995 Difficulty...

2287
来自专栏小樱的经验随笔

POJ 1012 Joseph

Joseph Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 53862 ...

3226
来自专栏小樱的经验随笔

HDU 2502 月之数(二进制,规律)

月之数 Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/...

3344
来自专栏算法修养

HDU 5877 2016大连网络赛 Weak Pair(树状数组,线段树,动态开点,启发式合并,可持久化线段树)

Weak Pair Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 262144/262144...

36910
来自专栏码匠的流水账

聊聊eureka client的fetch-remote-regions-registry属性

本文主要研究一下eureka client的fetch-remote-regions-registry属性

1101
来自专栏Hongten

spring开发_Annotation_注解

http://www.cnblogs.com/hongten/gallery/image/112614.html

761
来自专栏Jerry的SAP技术分享

使用com.sun.imageio.plugins.png.PNGMetadata读取图片的元数据

所谓图片元数据,就是除了我们肉眼看到的图片内容外,隐藏在这些内容背后的一些技术数据。

1464

扫码关注云+社区