您好,登錄后才能下訂單哦!
假期繼續(xù)刷題,也沒有別的什么事情可以干。
這個題是給出中序和后序遍歷隊(duì)列,構(gòu)造對應(yīng)二叉樹;題目很簡單,如下圖,給出兩個遍歷隊(duì)列,構(gòu)成二叉樹,這里假定沒有重復(fù)點(diǎn)。
想了好幾天,真是慚愧,因?yàn)橐恢毕胍淮伪闅v就完成構(gòu)造,最后發(fā)現(xiàn)不行;然后就硬搞出一個多重循環(huán)的遍歷方法,雖然可行,但是提交后提示耗時超過限制。最后還是用遞歸實(shí)現(xiàn)的。
其實(shí)原理很簡單,對于后續(xù)遍歷隊(duì)列,最后一個值就是整個二叉樹的根節(jié)點(diǎn);而這個根節(jié)點(diǎn)去掉后,可以把二叉樹分成左右兩個樹,在中序隊(duì)列中,按照這個根節(jié)點(diǎn)來拆分出可以得到左右隊(duì)列,分布對應(yīng)左邊樹和右邊樹的所有點(diǎn)。而且其實(shí)后序隊(duì)列也是按照左右樹節(jié)點(diǎn)劃分的,只要知道左右樹的節(jié)點(diǎn)數(shù)量,來劃分就可以了,這個可以從中序隊(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
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。