輸入某二叉樹(shù)的前序遍歷和中序遍歷的結(jié)果，請(qǐng)構(gòu)建該二叉樹(shù)并返回其根節(jié)點(diǎn)。

假設(shè)輸入的前序遍歷和中序遍歷的結(jié)果中都不含重復(fù)的數(shù)字。

最主要的就是找到確定遞歸的左右邊界~

不過(guò)我感覺(jué)preorder=preorder這一步的意義還是不太理解。

另外，字典特別容易和數(shù)組混啊，如果能用map解決就更直觀點(diǎn)了。

#前序遍歷?按照根節(jié)點(diǎn)|左節(jié)點(diǎn)|右節(jié)點(diǎn)進(jìn)行遍歷

#中序遍歷?按照左節(jié)點(diǎn)|根節(jié)點(diǎn)|右節(jié)點(diǎn)進(jìn)行遍歷

#1.前序遍歷的第一個(gè)元素為樹(shù)的根節(jié)點(diǎn)

#2.中序遍歷中，可根據(jù)找到的根節(jié)點(diǎn)劃分為[左子樹(shù)|根節(jié)點(diǎn)|右子樹(shù)]

#3.前序遍歷中，可根據(jù)中序遍歷中得到的左右子樹(shù)中節(jié)點(diǎn)的數(shù)量，劃分為[根節(jié)點(diǎn)|左子樹(shù)|右子樹(shù)]

#?例如：

#?preorder=[3,9,2,1,7]

#?inorder=[9,3,1,2,7]

#?得到3為樹(shù)的根節(jié)點(diǎn)，所以9為左子樹(shù)，2、1、7為右子樹(shù)，2為右子樹(shù)的根節(jié)點(diǎn)，因此1為右子樹(shù)的左子樹(shù)，7為右子樹(shù)的右子樹(shù)

#?思路：

#?1.找到根節(jié)點(diǎn)preorder[root]

#?2.在inorder中找到對(duì)應(yīng)preorder[root]的索引i，i左側(cè)的為左子樹(shù)，i右側(cè)的為右子樹(shù)

#?3.構(gòu)建左右子樹(shù)：

#?左子樹(shù)：根節(jié)點(diǎn)的索引?root+1(前序遍歷中左子樹(shù)在根節(jié)點(diǎn)右側(cè)，左子樹(shù)的根節(jié)點(diǎn)又是第一個(gè))

#?中序遍歷的左邊界?left

#?中序遍歷的右邊界?i-1

#?右子樹(shù)：根節(jié)點(diǎn)的索引?i+root-left+1（即根節(jié)點(diǎn)加上左子樹(shù)的長(zhǎng)度再加1）

#?中序遍歷的左邊界?i+1

#?中序遍歷的右邊界?right

#?當(dāng)left>right后，則已經(jīng)越過(guò)根節(jié)點(diǎn)，退出。

#?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,?preorder:?List[int],?inorder:?List[int])?->?TreeNode:

????????def?solve(root,left,right):

????????????if?left>right:?return

????????????node=TreeNode(preorder[root])

????????????i=dic[preorder[root]]

????????????node.left=solve(root+1,left,i-1)

????????????node.right=solve(i+root-left+1,i+1,right)

????????????return?node

????????dic={}

????????preorder=preorder

????????for?i?in?range(len(inorder)):

????????????dic[inorder[i]]=i

????????????#將inorder中的每個(gè)值和位子放入字典成為鍵值對(duì)，則可以根據(jù)preorder的值找到在inorder中的位置

????????return?solve(0,0,len(inorder)-1)

另外今天就摸到這里吧，?忍不住放個(gè)溫迪~