• <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 閱讀(221) 評論(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

            久久亚洲欧美日本精品| 久久精品国内一区二区三区 | 污污内射久久一区二区欧美日韩| 久久无码专区国产精品发布| 2019久久久高清456| 久久精品无码专区免费东京热| 国内精品久久久久久久97牛牛| 精品熟女少妇av免费久久| 久久99国产精品一区二区| 久久这里有精品视频| 欧美黑人激情性久久| 成人a毛片久久免费播放| 国产成人精品综合久久久| 国产视频久久| 国产一区二区三区久久精品| 久久国产精品无| 久久亚洲av无码精品浪潮| 精品久久人妻av中文字幕| 久久久久久久综合狠狠综合| 国产高潮久久免费观看| 久久99精品久久久久久久不卡 | 国产精品欧美久久久久天天影视| 久久夜色精品国产亚洲av| 久久久国产精品亚洲一区| 狠狠色婷婷久久一区二区| 香蕉aa三级久久毛片| 麻豆久久| 亚洲国产精品一区二区三区久久| 亚洲欧美精品伊人久久| 69久久精品无码一区二区| 亚洲va中文字幕无码久久不卡| 久久综合久久伊人| 国产福利电影一区二区三区久久久久成人精品综合 | 97久久超碰国产精品2021| 国产亚洲美女精品久久久2020| 国内精品久久久久久久coent| 99久久夜色精品国产网站| 国产午夜精品久久久久九九| 青青国产成人久久91网| 国产成人精品久久亚洲高清不卡 | 日本久久久久亚洲中字幕|