• <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 閱讀(164) 評論(0)  編輯 收藏 引用

            導航

            隨筆分類

            隨筆檔案

            最新評論

            国产亚洲精久久久久久无码77777| 亚洲精品成人久久久| 中文字幕日本人妻久久久免费| 思思久久好好热精品国产| 免费精品久久天干天干| 久久精品国产亚洲AV香蕉| 久久综合综合久久狠狠狠97色88| 999久久久免费国产精品播放| 日日狠狠久久偷偷色综合96蜜桃 | 亚洲香蕉网久久综合影视 | 色欲综合久久躁天天躁蜜桃| 久久国产乱子精品免费女| 欧洲性大片xxxxx久久久| 久久久久AV综合网成人| 久久久久久久国产免费看| 国内精品久久久久影院优| 亚洲伊人久久综合影院| 伊人色综合久久| 99久久中文字幕| 久久精品a亚洲国产v高清不卡| 天天影视色香欲综合久久| 日韩精品国产自在久久现线拍| 色狠狠久久综合网| 九九久久精品无码专区| 久久精品国产亚洲一区二区| 999久久久无码国产精品| 久久午夜无码鲁丝片秋霞| 亚洲精品美女久久久久99小说| 99国内精品久久久久久久| 91精品日韩人妻无码久久不卡| 久久久久久午夜成人影院| 色88久久久久高潮综合影院| 狠狠色噜噜色狠狠狠综合久久| 亚洲精品无码专区久久同性男 | 国产精品乱码久久久久久软件| 国产精品免费久久久久影院| 婷婷综合久久狠狠色99h| 久久综合九色综合欧美狠狠| 国产精品久久99| 一本大道久久a久久精品综合| 91久久香蕉国产熟女线看|