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

            国内精品久久久久久中文字幕| 久久久久久国产精品无码超碰| 一本伊大人香蕉久久网手机| 草草久久久无码国产专区| 久久久久夜夜夜精品国产| 国产农村妇女毛片精品久久| 午夜精品久久久久久影视riav | 精品少妇人妻av无码久久| 狠狠色丁香婷综合久久| 日韩久久久久中文字幕人妻| 色综合久久久久综合体桃花网| 99久久国产综合精品成人影院| 久久精品免费全国观看国产| 久久国产色AV免费观看| 亚洲伊人久久综合中文成人网| 久久99精品久久久久久久久久| 无码国内精品久久人妻麻豆按摩| 成人久久综合网| 色88久久久久高潮综合影院| 日本精品久久久久影院日本| 久久香蕉国产线看观看乱码| 亚洲国产另类久久久精品小说| 久久久久久久久久免免费精品| 久久成人国产精品| 久久久噜噜噜久久熟女AA片| 色欲综合久久躁天天躁蜜桃| 久久久久亚洲AV无码观看| 久久婷婷五月综合色99啪ak| 久久精品国产免费| 久久婷婷综合中文字幕| 欧美综合天天夜夜久久| 99热成人精品热久久669| 久久精品亚洲精品国产色婷| 人人狠狠综合久久88成人| 久久精品国产久精国产果冻传媒 | 91久久精一区二区三区大全| 无码人妻少妇久久中文字幕蜜桃| 精品人妻伦九区久久AAA片69| 久久伊人五月丁香狠狠色| 一本色道久久综合狠狠躁| 欧美黑人又粗又大久久久|