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个小时才解出来的Medium。。一种iterative解法
NOTE:
利用inorder 和 preorder的性质可知：
-
inorder是“左中右”，preorder是“中左右”，那么在“右”之前，“中左”和“左中”是完全逆序的，可以因此分片，如图：
-
如果是从inorder从左往右遍历，那么node1在搜索到的时候前面在preorder已经出现过了，所以更合理的分片是：蓝色竖线分割的5个分片。其中绿色删除掉的inorder元素在preorder已经出现过了。每个block内部是按照preorder顺序，每个元素都是前一个元素的左child。
- 还剩每个block第一个node是前面哪个node的右child还不确定。但这个parent其实就是当前这个block最后一个元素在inorder的前一个元素。比如6的parent就是7在inorder前面的2。
- 根据inorder的信息，6要么在1的左children里，或者6跟1有共同的祖先，6在一个左branch，1在右branch。6不可能在1的右children里。
- 根据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: 对preorder进行迭代
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
