題目出處
105. Construct Binary Tree from Preorder and Inorder Traversal
難度
medium
個人範例程式碼
# Definition for a binary tree node.
# 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 or not inorder:
return None
# preorder (M) L R
# inorder L (M) R
# use preorder get first node
val = preorder[0] # pre [(3),9,20,15,7], [(20),15,7]
root = TreeNode(val)
root_idx = inorder.index(val) # in [9,(3),15,20,7], [15,(20),7]]
# preorder[1:root_idx+1] del first, inorder[:root_idx]) del idx
root.left = self.buildTree(preorder[1:root_idx+1], inorder[0:root_idx])
# preorder[root_idx+1:], inorder[root_idx+1:]) del idx
root.right = self.buildTree(preorder[root_idx+1:], inorder[root_idx+1:])
return root
算法說明
看似複雜的問題，其實我們可以從「拆成很多子問題下手」，
因為就算是子樹，也會用一樣的概念去建構
有上面的觀念之後，看來就是 recursion 的回合了！
我們決定好怎麼定義我們的左右子樹，
root.left 的部分
我們直接拿題目來分析，
preorder 我們先拿了第一個，作為我們的 root [(3),9,20,15,7]，
之後我們要去找，有多少東西在左樹內，
我們需要去 inorder 找所有 root 左側的內容，
root_idx = inorder.index(val) # inorder [9,(3),15,20,7]
因此我們知道左側的 inorder 範圍：
inorder[:root_idx])，我們刪除已經被我們當 root 的點，位於 idx
而左側的 preorder 範圍：
我們必須刪除第一個點，因為他是我們的 root，剩下的範圍會到 root，
(取範圍時要注意取到 idx+1，才會是到「包含」 idx 的範圍)，
因此，preorder 我們取 preorder[1:root_idx+1]
合併後得到 root.left = self.buildTree(preorder[1:root_idx+1], inorder[0:root_idx])
root.right 的部分
右側的部分稍微簡單一點，在上方取得 idx 後，我們後面的範圍都是 right 的範圍了。
一樣以題目來舉例：
preorder [(3),9,20,15,7]
inorder [9,(3),15,20,7]
inorder idx 3 以後的內容，都會是我們右子樹的內容，包含 preorder 範圍也是如此。
因此我們得到 root.right = self.buildTree(preorder[root_idx+1:], inorder[root_idx+1:])
input handling
處理沒有 input 的情況，return None
或是處理只有一個值的情況 [-1]，return [-1]
Boundary conditions
用 not list 來控制範圍，表示已經沒有內容物