• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            Tree Recovery HEUOJ 1045 樹的遍歷

            Posted on 2012-04-26 13:32 lenohoo 閱讀(222) 評論(0)  編輯 收藏 引用

            Tree Recovery

            Description

            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!

            Input

            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.

            Output

            For each test case, recover Valentine's binary tree and print one line containing the tree's postorder traversal (left subtree, right subtree, root).

            Sample Input

            DBACEGF ABCDEFG
            BCAD CBAD

            Sample Output

            ACBFGED
            CDAB

            告訴你樹的先序遍歷,中序遍歷,求其后序遍歷
            #include<cstdio>
            #include
            <cstring>
            #include
            <iostream>
            using namespace std;
            char ch1[30],ch2[30],ch[30];
            int len;
            void dfs(int s1,int e1,int s2,int e2){
                
            if(s1>e1) return;
                ch[
            --len]=ch1[s1];
                
            int i;
                
            for(i=s2;ch2[i]!=ch1[s1] && i<=e2;i++);
                dfs(s1
            +i-s2+1,e1,i+1,e2);
                dfs(s1
            +1,s1+i-s2,s2,i-1);
            }
            int main(){
                
            while(~scanf("%s%s",ch1,ch2)){
                    len
            =strlen(ch1);
                    ch[len]
            ='\0';
                    dfs(
            0,len-1,0,len-1);
                    printf(
            "%s\n",ch);
                }
            }

            posts - 3, comments - 1, trackbacks - 0, articles - 16

            Copyright © lenohoo

            久久久久久国产a免费观看不卡| 日产久久强奸免费的看| 久久婷婷激情综合色综合俺也去| 77777亚洲午夜久久多人| 久久精品国产第一区二区三区| www.久久热| 久久亚洲AV无码精品色午夜麻豆| 久久A级毛片免费观看| 久久丝袜精品中文字幕| 久久久久99精品成人片直播| 久久久人妻精品无码一区| 久久人人爽人人爽人人片AV不| 97久久精品人人做人人爽| 亚洲欧美一级久久精品| 精品水蜜桃久久久久久久| 一本色道久久88—综合亚洲精品 | 久久久久亚洲精品无码网址| 99久久国语露脸精品国产| 亚洲伊人久久综合中文成人网| 久久精品国产99国产精偷| 久久亚洲AV成人无码电影| 午夜精品久久久久久影视riav| 国产精品狼人久久久久影院 | 国产精品久久久久久搜索| 国内精品伊人久久久久妇| 国产AV影片久久久久久| 国产精品久久久久aaaa| 久久久久久久97| 嫩草伊人久久精品少妇AV| 欧美久久天天综合香蕉伊| 94久久国产乱子伦精品免费| 久久青青草原精品影院| 久久精品国产亚洲AV香蕉| 国产毛片欧美毛片久久久| 久久免费视频1| 久久99久久99精品免视看动漫| 久久久久久久免费视频| 国产精品99久久久久久宅男小说| 狠狠色狠狠色综合久久| 三上悠亚久久精品| 国产精品一久久香蕉国产线看观看|