• <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

            中文字幕亚洲综合久久菠萝蜜| 国内精品久久久久久久久电影网 | 人妻无码αv中文字幕久久琪琪布 人妻无码精品久久亚瑟影视 | 久久综合给合久久狠狠狠97色69| 久久无码人妻一区二区三区| 91久久婷婷国产综合精品青草 | 香蕉久久夜色精品国产小说| 久久久噜噜噜久久中文字幕色伊伊| 久久久久久久人妻无码中文字幕爆 | 久久综合色之久久综合| 久久99精品久久久久久动态图 | 中文精品久久久久人妻| 久久香蕉超碰97国产精品| 久久精品18| 青青草国产成人久久91网| 日韩人妻无码精品久久久不卡| 亚洲国产精品久久久久网站| 亚洲国产精品久久久天堂| 老司机午夜网站国内精品久久久久久久久 | 久久天天躁狠狠躁夜夜2020| 久久人人爽人人爽人人片AV不| 久久亚洲国产午夜精品理论片| 亚洲精品成人网久久久久久| 国产A级毛片久久久精品毛片| 日本久久中文字幕| 久久成人永久免费播放| 久久av无码专区亚洲av桃花岛| 亚洲午夜无码久久久久小说| Xx性欧美肥妇精品久久久久久| 精品久久久久香蕉网| 亚洲精品乱码久久久久久按摩| 亚洲欧美久久久久9999| 久久人妻少妇嫩草AV蜜桃| 久久精品中文字幕第23页| 2020最新久久久视精品爱| 久久久久亚洲AV无码永不| 久久综合香蕉国产蜜臀AV| 久久国产精品77777| 91精品国产综合久久精品| 国产成人精品综合久久久久 | 亚洲国产成人久久综合一区77|