[LeetCode] #105. Construct Binary Tree from Preorder and Inorder Traversal
題目
Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree.
直覺解
構想：
有稍微偷看一下 Solution 區的分析。
交叉對照 preorder 和 inorder，以找出 root、left subtree 和 right subtree。
preorder[0] 是 root
inorder 中，root 的左邊是 left subtree，右邊是 right subtree
python 3 實作（失敗）：
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
if not preorder:
return None
if len(preorder) == 1:
return TreeNode(preorder[0])
root = TreeNode(preorder[0])
inorder_left = inorder[0:inorder.index(root.val)]
inorder_right = inorder[inorder.index(root.val)+1:]
preorder_left = preorder[1:preorder.index(inorder_left[-1])+1]
preorder_right = preorder[preorder.index(inorder_left[-1])+1:]
root.left = self.buildTree(preorder_left, inorder_left)
root.right = self.buildTree(preorder_right, inorder_right)
return root
Submission Detail
Runtime Error Message: IndexError: list index out of range
Last executed input:
[1,2]
[1,2]
失敗原因
inorder_left 是 []，所以 inorder_left[-1] 會報錯
構想：
inorder_left 不是 [] 的話，才使用 inorder_left[-1] 語法
python 3 實作（失敗）：
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
if not preorder:
return None
if len(preorder) == 1:
return TreeNode(preorder[0])
root = TreeNode(preorder[0])
inorder_left = inorder[0:inorder.index(root.val)]
inorder_right = inorder[inorder.index(root.val)+1:]
preorder_left = []
preorder_right = []
if len(inorder_left) > 0:
preorder_left = preorder[1:preorder.index(inorder_left[-1])+1]
preorder_right = preorder[preorder.index(inorder_left[-1])+1:]
else:
preorder_right = preorder[preorder.index(root.val)+1:]
root.left = self.buildTree(preorder_left, inorder_left)
root.right = self.buildTree(preorder_right, inorder_right)
return root
Submission Detail
Wrong Answer
Input:
[1,2,3]
[3,2,1]
Output: [1,2,3]
Expected: [1,2,null,3]
失敗原因
切 left subtree 時切錯了。inorder_left 是正確的 [3, 2]，但是 preorder_left 是 [2]。
構想：
切 preorder_subtree 時，改成根據 inorder_subtree 的長度去切，不要根據inorder_subtree[-1] 的位置去切。
python 3 實作：
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
if not preorder:
return None
if len(preorder) == 1:
return TreeNode(preorder[0])
root = TreeNode(preorder[0])
inorder_left = inorder[0:inorder.index(root.val)]
inorder_right = inorder[inorder.index(root.val)+1:]
preorder_left = preorder[1:len(inorder_left)+1]
preorder_right = preorder[len(inorder_left)+1:]
root.left = self.buildTree(preorder_left, inorder_left)
root.right = self.buildTree(preorder_right, inorder_right)
return root
效能：
Runtime: 224 ms, faster than 17.33% of Python3 online submissions for Construct Binary Tree from Preorder and Inorder Traversal.
Memory Usage: 88.4 MB, less than 19.53% of Python3 online submissions for Construct Binary Tree from Preorder and Inorder Traversal.
研究別人的解
來源：sample 136 ms submission
研究重點：如何改善效能。
別人的 python 3 實作：
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
if inorder:
root = preorder.pop(0)
index = inorder.index(root)
root = TreeNode(root)
root.left = self.buildTree(preorder, inorder[:index])
root.right = self.buildTree(preorder, inorder[index + 1:])
return root
效能：
Runtime: 136 ms, faster than 52.96% of Python3 online submissions for Construct Binary Tree from Preorder and Inorder Traversal.
Memory Usage: 53 MB, less than 49.93% of Python3 online submissions for Construct Binary Tree from Preorder and Inorder Traversal.
研究感想
preorder 的用途是找出 root。靠 preorder.pop(0) 和 python 傳遞 preorder 的方式，那麼每次呼叫 buildTree 時，preorder 裡面自然只會剩下跟 inorder 一樣多的元素。
這樣就不需要再計算 preorder_left 和 preorder_right 分別是多少了，節省計算時間。這個傳遞 preorder 的方式，不會複製新的 list，節省了使用的記憶體。
研究別人的解
來源：sample 56 ms submission
研究重點：如何改善效能。
別人的 python 3 實作：
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
def array_to_tree(left, right):
nonlocal p
# if there are no elements to construct the tree
if left > right: return None
# the current element in preorder is the root of this subtree
root = TreeNode(preorder[p])
p += 1
# build left and right subtrees under this root
# exclude inorder_v2i[root.val] element because it's the root
root.left = array_to_tree(left, inorder_v2i[root.val] - 1)
root.right = array_to_tree(inorder_v2i[root.val] + 1, right)
return root
p = 0 # preorder list index
# map values to indices in the inorder list so can look up index by value
inorder_v2i = {v: i for (i, v) in enumerate(inorder)} # value to index -- a dict comprehension!
# https://stackoverflow.com/questions/1747817/create-a-dictionary-with-list-comprehension
return array_to_tree(0, len(preorder) - 1)
效能：
Runtime: 48 ms, faster than 98.37% of Python3 online submissions for Construct Binary Tree from Preorder and Inorder Traversal.
Memory Usage: 19 MB, less than 70.25% of Python3 online submissions for Construct Binary Tree from Preorder and Inorder Traversal.
研究感想
把 inorder 轉成 dictionary，加快用 value 查詢 index 的速度。
不複製 inorder 也不複製 preorder，節省記憶體空間。array_to_tree 接受的參數是 inorder 的 index。不刪除 preorder 中的元素，只依靠 p 的變動紀錄 root 的 index。
研究別人的解
來源：sample 36 ms submission
研究重點：不用遞迴的寫法。
別人的 python 3 實作：
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
T = [TreeNode(12000003)]
p = 0
i = 0
LEFT, RIGHT = 1, 2
direction = LEFT
D = {}
while p < len(preorder) and i < len(inorder):
pre = preorder[p]
inn = inorder[i]
# exist in T
if inn in D:
#T = T[:D[inn]+1]
del T[D[inn]+1:]
direction = RIGHT
i += 1
elif inn == pre:
node = TreeNode(pre)
if direction == LEFT:
T[-1].left = node
else:
T[-1].right = node
T.append(node)
D[pre] = len(T) - 1
direction = RIGHT
p+=1
i+=1
else:
node = TreeNode(pre)
if direction == LEFT:
T[-1].left = node
else:
T[-1].right = node
T.append(node)
D[pre] = len(T) - 1
direction = LEFT
p+=1
#print(T)
return T[1]
效能：
Runtime: 52 ms, faster than 94.45% of Python3 online submissions for Construct Binary Tree from Preorder and Inorder Traversal.
Memory Usage: 17.7 MB, less than 99.82% of Python3 online submissions for Construct Binary Tree from Preorder and Inorder Traversal.
研究感想
T 用來存創造出的所有 TreeNode，T[0] 是 dummy root。p 和 i 分別紀錄 preorder 和 inorder 目前迭代到哪個 index。D 用來快速查詢「val 是某某值的 TreeNode 在 T 的哪個 index」。direction 代表這個節點要接在 T[-1] 這個節點的左邊或右邊。
用 preorder = [1, 2, 3], inorder = [3, 2, 1] 帶入來看的話，因為這組 input 只有長左邊的節點，所以 while 迴圈中有執行到的部分只有：
while p < len(preorder) and i < len(inorder):
pre = preorder[p]
inn = inorder[i]
# exist in T
if inn in D:
#T = T[:D[inn]+1]
del T[D[inn]+1:]
direction = RIGHT
i += 1
elif inn == pre:
node = TreeNode(pre)
if direction == LEFT:
T[-1].left = node
else:
T[-1].right = node
T.append(node)
D[pre] = len(T) - 1
direction = RIGHT
p+=1
i+=1
else:
node = TreeNode(pre)
if direction == LEFT:
T[-1].left = node
else:
T[-1].right = node
T.append(node)
D[pre] = len(T) - 1
direction = LEFT
p+=1
用 preorder = [1, 2], inorder = [1, 2] 帶入來看的話，因為這組 input 只有長右邊的節點，所以 while 迴圈中有執行到的部分只有：
while p < len(preorder) and i < len(inorder):
pre = preorder[p]
inn = inorder[i]
# exist in T
if inn in D:
#T = T[:D[inn]+1]
del T[D[inn]+1:]
direction = RIGHT
i += 1
elif inn == pre:
node = TreeNode(pre)
if direction == LEFT:
T[-1].left = node
else:
T[-1].right = node
T.append(node)
D[pre] = len(T) - 1
direction = RIGHT
p+=1
i+=1
else:
node = TreeNode(pre)
if direction == LEFT:
T[-1].left = node
else:
T[-1].right = node
T.append(node)
D[pre] = len(T) - 1
direction = LEFT
p+=1
用 preorder = [1, 2, 3], inorder = [2, 1, 3] 帶入來看的話，因為這組 input 只有長右邊的節點，所以 while 迴圈中有執行到的部分只有：
while p < len(preorder) and i < len(inorder):
pre = preorder[p]
inn = inorder[i]
# exist in T
if inn in D:
#T = T[:D[inn]+1]
del T[D[inn]+1:]
direction = RIGHT
i += 1
elif inn == pre:
node = TreeNode(pre)
if direction == LEFT:
T[-1].left = node
else:
T[-1].right = node
T.append(node)
D[pre] = len(T) - 1
direction = RIGHT
p+=1
i+=1
else:
node = TreeNode(pre)
if direction == LEFT:
T[-1].left = node
else:
T[-1].right = node
T.append(node)
D[pre] = len(T) - 1
direction = LEFT
p+=1
if inn in D 那一段的作用：因為每次都是幫 T[-1] 增加子節點，加完之後就把新的節點 append 到 T 裡，所以，如果某個節點同時有兩個子節點 A, B，而 A 已經先掛到父節點底下的話，就需要把 T 裡面的 A 節點刪掉，才能用 T[-1] 的方式選到 A 的父節點，再把 B 節點掛上去。
Comments
Post a Comment