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

相关文章

  • 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),...

    书童小二
  • 如何为ABAP类创建隐式增强

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

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

    FlyLolo
  • 云基础虚拟网络的有效欺骗网络体系(CS CR)

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

    Elva
  • 剑指offer04--重建二叉树

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

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

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

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

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

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

    AI科技评论

扫码关注云+社区

领取腾讯云代金券