Description:
Given preorder and inorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
For example, given
preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]
Return the following binary tree:
Solutions:
Solution1: 搞了2個(gè)小時(shí)才解出來(lái)的Medium耍目。瓢喉。一種iterative解法
NOTE:
利用inorder 和 preorder的性質(zhì)可知：
-
inorder是“左中右”拙友，preorder是“中左右”茉盏，那么在“右”之前，“中左”和“左中”是完全逆序的瘦真，可以因此分片属铁，如圖：
-
如果是從inorder從左往右遍歷憎夷，那么node1在搜索到的時(shí)候前面在preorder已經(jīng)出現(xiàn)過(guò)了，所以更合理的分片是：藍(lán)色豎線分割的5個(gè)分片躬柬。其中綠色刪除掉的inorder元素在preorder已經(jīng)出現(xiàn)過(guò)了拜轨。每個(gè)block內(nèi)部是按照preorder順序，每個(gè)元素都是前一個(gè)元素的左child允青。
- 還剩每個(gè)block第一個(gè)node是前面哪個(gè)node的右child還不確定橄碾。但這個(gè)parent其實(shí)就是當(dāng)前這個(gè)block最后一個(gè)元素在inorder的前一個(gè)元素。比如6的parent就是7在inorder前面的2颠锉。
- 根據(jù)inorder的信息法牲，6要么在1的左children里，或者6跟1有共同的祖先琼掠，6在一個(gè)左branch皆串，1在右branch。6不可能在1的右children里眉枕。
- 根據(jù)preorder的信息，6要么是1的子孫怜森，要么跟1有共同祖先速挑，但是6在右branch，1在左branch副硅。
因此6不是1的右child姥宝，在1的左children里面。
=> 6是7之前的2的right child恐疲。后面以此類推腊满，8是6的right child，9是1的right child培己，11是9的right child
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
if not preorder:
return None
dic = {}
for i,n in enumerate(preorder):
dic[n] = i
last_head = preorder.index(inorder[0])
node_hist = [TreeNode(preorder[i]) for i in range(last_head+1)]
for k in range(len(node_hist)-1):
node_hist[k].left = node_hist[k+1]
i = 1
j = last_head+1
while j < len(preorder):
index = dic[inorder[i]]
if index >= j:
cache = [TreeNode(preorder[k]) for k in range(j,index+1)]
for k in range(len(cache)-1):
cache[k].left = cache[k+1]
node_hist[last_head].right = cache[0]
node_hist += cache
last_head = index
i += 1
j = max(j,last_head+1)
return node_hist[0]
Runtime: 48 ms, faster than 93.19% of Python3 online submissions for Construct Binary Tree from Preorder and Inorder Traversal.
Memory Usage: 14.3 MB, less than 95.75% of Python3 online submissions for Construct Binary Tree from Preorder and Inorder Traversal.
Solution2: 一種遞推的解法
inspired by http://bangbingsyb.blogspot.com/2014/11/leetcode-construct-binary-tree-from.html
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
if not preorder:
return None
root_val = preorder[0]
root = TreeNode(root_val)
index = inorder.index(root_val)
root.left = self.buildTree(preorder[1:index+1],inorder[:index])
root.right = self.buildTree(preorder[index+1:],inorder[index+1:])
return root
Runtime: 188 ms, faster than 36.89% of Python3 online submissions for Construct Binary Tree from Preorder and Inorder Traversal.
Memory Usage: 87.8 MB, less than 19.44% of Python3 online submissions for Construct Binary Tree from Preorder and Inorder Traversal.
sample 120 ms submission:
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
if not inorder or not preorder:
return None
ind = inorder.index(preorder.pop(0))
root = TreeNode(inorder[ind])
root.left = self.buildTree(preorder, inorder[:ind])
root.right = self.buildTree(preorder, inorder[ind+1:])
return root
sample 36 ms submission:
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
#get root from preorder
# save index from inorder to find range of index between which left and right child will be
ln = len(inorder)
mp = {}
for idx, num in enumerate(inorder):
mp[num] = idx
l, r = 0, ln - 1
self.idx = 0 #idx is for preorder
return self.helper(preorder, mp, l, r)
def helper(self, preorder, mp, l, r):
if l > r:
return None
num = preorder[self.idx]
newNode = TreeNode(num)
self.idx += 1
if l == r:
return newNode
else:
newNode.left = self.helper(preorder, mp, l, mp[num]-1)
newNode.right = self.helper(preorder, mp, mp[num]+1, r)
return newNode
sample 32 ms submission: 對(duì)preorder進(jìn)行迭代
class Solution:
def buildTree(self, preorder, inorder):
ind = {}
for i,v in enumerate(inorder):
ind[v] = i
stack, root = [], None
for val in preorder:
if not root:
root = TreeNode(val)
stack.append(root)
else:
idx = ind[val]
node = TreeNode(val)
if idx < ind[stack[-1].val]:
stack[-1].left = node
else:
while stack and idx > ind[stack[-1].val]:
parent = stack.pop()
parent.right = node
stack.append(node)
return root
