題目出處
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 來控制範圍,表示已經沒有內容物
Reference
⭐ Leetcode 解題紀錄 ⭐ | 題型 | 資料結構 | Python Solution | C++ Solution | Note | |
---|---|---|---|---|---|---|
⭐BFS 相關題型 ⭐ | ||||||
104 | Maximum Depth of Binary Tree | BFS (分層) | Python | |||
94 | Binary Tree Inorder Traversal | BFS (分層) | Tree | Python | 內含 處理 Tree 樹問題的重點 | |
102 | Binary Tree Level Order Traversal | BFS (分層) | Tree | Python | ||
103 | Binary Tree Zigzag Level Order Traversal | BFS (分層) | Tree | Python | ||
107 | Binary Tree Level Order Traversal II | BFS (分層) | Tree | Python | ||
133 | Clone Graph | BFS (分層) | Graph | Python | Graph 的基本操作 #重要題型 | |
127 | Word Ladder | BFS (分層), DFS | Graph | Python | ||
[Lint] 127 | Topological Sorting | BFS (拓撲) |