項目 widget-area-1 尚未註冊或是沒有一個 view.php 檔案.
項目 widget-area-1 尚未註冊或是沒有一個 view.php 檔案.
項目 search-input 尚未註冊或是沒有一個 view.php 檔案.

【Leetcode】python – [105] Construct Binary Tree from Preorder and Inorder Traversal 個人解法筆記

題目出處

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 SolutionC++ SolutionNote
⭐BFS 相關題型 ⭐
104Maximum Depth of Binary TreeBFS (分層)Python
94Binary Tree Inorder TraversalBFS (分層)TreePython 內含 處理 Tree 樹問題的重點
102Binary Tree Level Order TraversalBFS (分層)TreePython
103Binary Tree Zigzag Level Order TraversalBFS (分層)TreePython
107Binary Tree Level Order Traversal IIBFS (分層)TreePython
133Clone GraphBFS (分層)GraphPython Graph 的基本操作 #重要題型
127Word LadderBFS (分層), DFSGraphPython
[Lint] 127Topological SortingBFS (拓撲)