刷題系列-中序和后序遍歷隊(duì)列，構(gòu)造對應(yīng)二叉樹；

假期繼續(xù)刷題，也沒有別的什么事情可以干。

10年積累的成都網(wǎng)站制作、成都網(wǎng)站建設(shè)經(jīng)驗(yàn)，可以快速應(yīng)對客戶對網(wǎng)站的新想法和需求。提供各種問題對應(yīng)的解決方案。讓選擇我們的客戶得到更好、更有力的網(wǎng)絡(luò)服務(wù)。我雖然不認(rèn)識你，你也不認(rèn)識我。但先網(wǎng)站策劃后付款的網(wǎng)站建設(shè)流程，更有嘉黎免費(fèi)網(wǎng)站建設(shè)讓你可以放心的選擇與我們合作。

這個(gè)題是給出中序和后序遍歷隊(duì)列，構(gòu)造對應(yīng)二叉樹；題目很簡單，如下圖，給出兩個(gè)遍歷隊(duì)列，構(gòu)成二叉樹，這里假定沒有重復(fù)點(diǎn)。

 

想了好幾天，真是慚愧，因?yàn)橐恢毕胍淮伪闅v就完成構(gòu)造，最后發(fā)現(xiàn)不行；然后就硬搞出一個(gè)多重循環(huán)的遍歷方法，雖然可行，但是提交后提示耗時(shí)超過限制。最后還是用遞歸實(shí)現(xiàn)的。

其實(shí)原理很簡單，對于后續(xù)遍歷隊(duì)列，最后一個(gè)值就是整個(gè)二叉樹的根節(jié)點(diǎn)；而這個(gè)根節(jié)點(diǎn)去掉后，可以把二叉樹分成左右兩個(gè)樹，在中序隊(duì)列中，按照這個(gè)根節(jié)點(diǎn)來拆分出可以得到左右隊(duì)列，分布對應(yīng)左邊樹和右邊樹的所有點(diǎn)。而且其實(shí)后序隊(duì)列也是按照左右樹節(jié)點(diǎn)劃分的，只要知道左右樹的節(jié)點(diǎn)數(shù)量，來劃分就可以了，這個(gè)可以從中序隊(duì)列劃分結(jié)果獲得。反復(fù)同理，再劃分出來左右樹繼續(xù)劃分，可以得到葉子節(jié)點(diǎn)，或者空序列；這樣就完成樹的構(gòu)成。

代碼如下：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
        if inorder == []:
            return None
        else:
            if len(inorder) == 1:
                return TreeNode(inorder[0])
            else:
                RootVal = postorder[-1]
                currentNode = TreeNode(RootVal)
                inorderLeft = inorder[:inorder.index(RootVal)]
                inorderRight = inorder[inorder.index(RootVal)+1:]
                postorder.pop()
                postorderLeft = postorder[:len(inorderLeft)]
                postorderRight = postorder[-len(inorderRight):] 
                currentNode.left = self.buildTree(inorderLeft,postorderLeft)
                currentNode.right = self.buildTree(inorderRight,postorderRight)
                return currentNode

  

網(wǎng)站標(biāo)題：刷題系列-中序和后序遍歷隊(duì)列，構(gòu)造對應(yīng)二叉樹；
文章出自：http://www.muchs.cn/article40/jpcoho.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站設(shè)計(jì)、微信小程序、App設(shè)計(jì)、搜索引擎優(yōu)化、服務(wù)器托管、虛擬主機(jī)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)