• <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>
            posts - 195,  comments - 30,  trackbacks - 0
            Leaf Nodes
            Status In/Out TIME Limit MEMORY Limit Submit Times Solved Users JUDGE TYPE
            stdin/stdout 1s 10240K 222 102 Standard

            Kate is learning about binary tree. She think she know everything you know about binary trees. Wait, you don't know binary tree? Find a book about data structures, and it will just take you about three minutes. Now here is a binary tree:

                                                3
            / \
            /   \
            2     4
            / \     \
            /   \     \
            0     1     6
            /
            /
            5
            

            Kate think she also know something that you may not notice. First, for some type of binary trees, only the leaf nodes have the meaning (leaf node is the node which has no sub trees, for the tree above, the leaf nodes are 0 1 5), an example is the Huffman Tree. Second, she guess that if you know the preorder traversal and the postorder traversal of a binary tree, you can ensure the leaf node of the tree, and their order.

            For the tree above, the preorder travesal is 3 2 0 1 4 6 5 and the postorder travesal is 0 1 2 5 6 4 3, the leaf nodes in order(from left to right) are 0 1 5.

            But now the problem is she just guess it, if you can find a way to print a tree's leaf nodes in order using its preorder traversal and postorder traversal, you can say "she is right!"

            Input Specification

            The input file will contain one or more test cases. In each test case there is a integer n (0<=n <= 10000), indicating the tree have n nodes, then followed two lists of integers, either contains n integers in the range of 0 and n-1 (both included), the first list is the preorder traversal, and the other is the postorder traversal.

            Input is terminated by an interger -1;

            Output Specification

            For each test case, print the tree's leaf nodes in order, each in a line.

            Sample Input

            7
            3 2 0 1 4 6 5
            0 1 2 5 6 4 3
            -1

            Sample Output

            0
            1
            5
            根據一個重要結論,無論是先根還是后根遍歷,左子樹的結點總是出現在右子樹結點的前面

                                             G  
                                            /   \  
                                          F        B  
                                        /        /   \  
                                      K         C      H  
                                    /   \             /        
                                  D       E         J  
                                    \  
                                      A  
                                    /  
                                  I  
               
              不論先根后根,左子樹的結點總是出現在右子樹結點的前面。  
              G為根樹,先根次序時G后跟F,后根次序時F前有DIAEKF,故DIAEKF為G的左子樹的結點,
              CJHB為G的右子樹的結點。且左右子樹的先根序為:FKDIAE,BCHJ。
              遞歸處理兩子樹即可搞定

            void  find(int preb,int pree,int postb,int poste) 
               {
               int i=s(pre,post[poste-1]);
              int j=s(post,pre[preb+1]);
            //添加處理的代碼
             //判斷是否有左/右支

                find(preb+1,i-1,postb,j);
              find(i,pree,j+1,poste-1);
               }
            但是上面的思路是錯誤的?。。。。。。。。。。。。?!
            只知道先序和后序不能能推出樹來  
               
              只有中序和先序或者中序和后序才可以  
               
              不然只知道根節點,但是哪些是左子樹哪些是右子樹就不知道了
            比如先序時1234  
              后序是4321的二叉樹有8種比如:  
                  1                     1              
                  \                   /  
                    2               2  
                /                 /  
              3                 3  
                \             /  
                  4         4

            正確思路:先遍歷后根次序,第一個一定為葉子,設為當前結點,然后依次檢測,如果該點在先根序列中位于當前節點的后面,則為葉子節點,同時更新當前結點。
            posted on 2009-07-14 22:14 luis 閱讀(277) 評論(0)  編輯 收藏 引用 所屬分類: 圖論*矩陣
            <2011年5月>
            24252627282930
            1234567
            891011121314
            15161718192021
            22232425262728
            2930311234

            常用鏈接

            留言簿(3)

            隨筆分類

            隨筆檔案

            文章分類

            文章檔案

            友情鏈接

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            狠狠综合久久综合88亚洲 | 日本精品久久久久久久久免费| 国产91色综合久久免费分享| 欧美精品丝袜久久久中文字幕 | 亚洲综合伊人久久综合| 久久亚洲精品成人av无码网站| 亚洲欧洲久久av| 26uuu久久五月天| 国产精品久久自在自线观看| 久久人人爽人人爽人人片AV东京热 | 无码专区久久综合久中文字幕| 久久这里只有精品视频99| 久久精品国产日本波多野结衣| 久久青青草原国产精品免费 | 欧美一区二区久久精品| 亚洲国产日韩欧美综合久久| 久久综合综合久久综合| 久久综合精品国产一区二区三区| 国产精品一久久香蕉国产线看观看| 亚洲午夜久久久久久久久电影网| 久久天堂电影网| 91久久精一区二区三区大全| 久久www免费人成看片| 久久最新免费视频| 99久久国产综合精品网成人影院| 久久人人爽人人爽人人AV东京热 | 久久午夜无码鲁丝片| 久久这里只有精品首页| 亚洲伊人久久大香线蕉综合图片| 激情久久久久久久久久| 一97日本道伊人久久综合影院| 伊人久久大香线焦综合四虎| 国产亚洲精品美女久久久| 人妻无码αv中文字幕久久 | 亚洲综合精品香蕉久久网| 精品久久亚洲中文无码| 怡红院日本一道日本久久| 国产精品99久久久久久宅男| 婷婷久久精品国产| 亚洲国产成人精品91久久久 | 无码专区久久综合久中文字幕 |