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

            導航

            隨筆分類

            隨筆檔案

            最新評論

            欧美成人免费观看久久| 69国产成人综合久久精品| 久久人搡人人玩人妻精品首页| 国内精品欧美久久精品| 中文字幕精品无码久久久久久3D日动漫 | 无码国内精品久久综合88| 欧美久久久久久| 久久久久人妻精品一区| 欧美精品福利视频一区二区三区久久久精品| 亚洲国产精品狼友中文久久久| 亚洲精品白浆高清久久久久久| 久久精品国产只有精品2020| 国内精品伊人久久久久妇| av国内精品久久久久影院| 99久久国产亚洲综合精品| 久久精品www| 久久精品国产亚洲AV大全| 精品久久久久成人码免费动漫| 久久久久夜夜夜精品国产| 久久er99热精品一区二区| 性高朝久久久久久久久久| 国产成人香蕉久久久久| 2021少妇久久久久久久久久| 成人午夜精品无码区久久| 久久亚洲色一区二区三区| 97久久精品人人做人人爽| 久久国产高清字幕中文| 色狠狠久久AV五月综合| 久久AV高潮AV无码AV| 久久无码高潮喷水| 久久精品国产亚洲AV影院| 亚洲国产视频久久| 亚洲婷婷国产精品电影人久久| 久久精品无码一区二区三区免费| 很黄很污的网站久久mimi色| 精品久久久久一区二区三区| 精品无码人妻久久久久久| 精品久久久久久久中文字幕 | 久久久久人妻一区精品色 | 久久这里只有精品视频99| 一本久久a久久精品综合香蕉|