您好,登錄后才能下訂單哦!
如何從前序與中序遍歷序列構(gòu)造python二叉樹,很多新手對此不是很清楚,為了幫助大家解決這個難題,下面小編將為大家詳細講解,有這方面需求的人可以來學(xué)習(xí)下,希望你能有所收獲。
【題目】
根據(jù)一棵樹的前序遍歷與中序遍歷構(gòu)造二叉樹。
注意: 你可以假設(shè)樹中沒有重復(fù)的元素。
例如,給出
前序遍歷 preorder = [3,9,20,15,7]
中序遍歷 inorder = [9,3,15,20,7]
返回如下的二叉樹:
3
/ \
9 20
/ \
15 7
【思路】
首先回顧遍歷的順序:前序遍歷是根節(jié)點-左子樹-右子樹,中序遍歷是左子樹-根節(jié)點-右子樹。
那么前序遍歷數(shù)組的第一個元素肯定是根節(jié)點,在中序遍歷數(shù)組中找到這個元素,則其前一部分是左子樹的元素,其后一部分是右子樹的元素。遞歸即可求解。
注意:前序遍歷+后序遍歷,不能確定唯一的二叉樹!
【代碼】
python版本
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def buildTree(self, preorder, inorder):
"""
:type preorder: List[int]
:type inorder: List[int]
:rtype: TreeNode
"""
# 前序遍歷,第一個是head
# 中序遍歷,前一部分是左子樹,后一部分是右子樹
if len(preorder) == 0:
return None
node = TreeNode(preorder[0])
index = inorder.index(preorder[0])
node.left = self.buildTree(preorder[1: index + 1], inorder[:index])
node.right = self.buildTree(preorder[index + 1:], inorder[index + 1:])
return node
【相似題目】
從中序與后序遍歷序列構(gòu)造二叉樹
解題思路:后序遍歷數(shù)組的最后一個元素是根節(jié)點的元素,同樣在中序遍歷數(shù)組中找到該元素,遞歸生成二叉樹。
根據(jù)前序和后序遍歷構(gòu)造二叉樹
解題思路:直接生成只有右孩子的二叉樹即可滿足條件。
看完上述內(nèi)容是否對您有幫助呢?如果還想對相關(guān)知識有進一步的了解或閱讀更多相關(guān)文章,請關(guān)注億速云行業(yè)資訊頻道,感謝您對億速云的支持。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進行舉報,并提供相關(guān)證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權(quán)內(nèi)容。