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

            GLORY | 學習·記錄

            coding for life

            POJ 2255 Tree Recovery

            根據先序和中序確定后序的題目,非常經典的數據結構題目。

            假如有一棵樹的先序遍歷是
            DBACEGF,后序遍歷是ABCDEFG。
            因為先序遍歷是根節點-左子樹-右子樹,所以可以確定D是這顆樹的根節點。
            考慮中序遍歷是左子樹-根節點-右子樹,所以中序的序列被根節點分成了兩個部分,在這里就是ABC和EFG,分別是左子樹和右子樹。
            接下來可以確定的以D為根節點的數的左子樹的先序遍歷為BAC(節點個數根據中序的左子樹節點個數確定),右子樹的先序遍歷為EGF.
            這樣,我們的問題就轉化成為了與源問題相同的兩個子問題,那么就可以通過遞歸來實現,結束的條件就是子樹只剩一個節點,這個時候先序和中序是一樣的,打印出來,然后return到上一級。
            綜上,解決辦法就是現找到根節點,然后根據中序列劃分成兩個部分,然后分別遞歸解決。
            需要注意的是,可能出現這樣的狀況:先序為AB,中序為BA;或者先序為AB,中序為AB的情況。即劃分子樹的時候可能右子樹或者左子樹為空
            所以需要加一個判斷,就是是否用來指示序列的左指針已經大于右指針。

            POJ 3094  Quicksum實在太水,提一聲就ok。

            posted on 2010-07-14 23:44 meglory 閱讀(165) 評論(0)  編輯 收藏 引用

            導航

            隨筆分類

            隨筆檔案

            最新評論

            久久久久综合国产欧美一区二区| 97精品伊人久久大香线蕉app| 久久本道久久综合伊人| 精品国产青草久久久久福利| 久久久久久精品免费免费自慰| 国产高潮国产高潮久久久| 久久国产精品一区| 久久精品无码一区二区无码 | 国产V亚洲V天堂无码久久久| 久久精品国产精品青草app| 伊人久久精品影院| 久久99精品国产麻豆宅宅| 日产精品久久久久久久| 久久亚洲精品视频| 日本欧美久久久久免费播放网| 国产综合精品久久亚洲| 99久久久国产精品免费无卡顿| 2020国产成人久久精品| 久久久99精品成人片中文字幕| 成人久久精品一区二区三区| 精品国产乱码久久久久久呢| 久久亚洲av无码精品浪潮| 伊人热人久久中文字幕| 2021久久国自产拍精品| 欧美熟妇另类久久久久久不卡| 日韩亚洲国产综合久久久| 国产高潮国产高潮久久久91 | 蜜臀av性久久久久蜜臀aⅴ麻豆| 久久久久亚洲av成人无码电影 | 97精品国产97久久久久久免费| 日本久久中文字幕| 伊人久久亚洲综合影院| 日韩影院久久| 亚洲午夜精品久久久久久app| 久久久久久A亚洲欧洲AV冫| 久久天天躁狠狠躁夜夜2020| 久久久久久极精品久久久| 久久久久久毛片免费看| 久久人人爽人人精品视频| 精品国产乱码久久久久软件 | 久久亚洲美女精品国产精品|