# **Leetcode筆記(Construct Binary Tree from Preorder and Inorder Traversal)** :::info :information_source: 題目 : Construct Binary Tree from Preorder and Inorder Traversal, 類型 : binary tree , 等級 : medium 日期 : 2023/03/18，2023/05/24，2023/07/07，2024/10/18 ::: ### 嘗試 時間複雜度O(n)，空間複雜度O(n) ```python class Solution: def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]: # 前序 (preorder): 中 -> 左 -> 右 # 中序 (inorder): 左 -> 中 -> 右 res = list() leftl = list() rightl = list() res.append(root) for i < len(inorder): if inorder[i] == preorder[0]: node = preorder leftl = inorder[0, i] rightl = inorder[i, 0] ``` 2023/05/24 ```python class Solution: def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]: # 前序 (preorder): 中 -> 左 -> 右 # 中序 (inorder): 左 -> 中 -> 右 if not preorder and not inorder: return None root = TreeNode(preorder[0]) # 在inorder的mid mid = inorder.index(preorder[0]) # 不包含root -> preorder[1 : mid + 1] root.left = self.buildTree(preorder[1 : mid + 1], inorder[ : mid]) root.right = self.buildTree(preorder[mid + 1: ], inorder[mid + 1 : ]) return root ``` 2023/07/07 可以畫[這裡](https://www.youtube.com/watch?v=wDsFfgv4OGY)這種123方法去思考遞迴 每個node都會有當到root的機會，會先處理最左邊的那個node，並把結果回傳給上一層的root.left 步驟 : 一開始先抓住preorder[0]，在去inorder抓index，分辨left和right ```python class Solution: def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]: if not preorder or not inorder: return None root = TreeNode(preorder[0]) index = inorder.index(preorder[0]) # 分界index root.left = self.buildTree(preorder[1 : index + 1], inorder[0 : index]) root.right = self.buildTree(preorder[index + 1 : ], inorder[index + 1 : ]) return root ``` 如果有preorder[:0]的話，會是取到空字串，不會有錯誤，照樣可以被視為list傳 要記得，如果是取pre/in，需要撇開root，然後pre/in的list長度會相同 可以用list.index去取index ```python class Solution: def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]: if not preorder or not inorder: return None root = TreeNode(preorder[0]) i = inorder.index(preorder[0]) root.left = self.buildTree(preorder[1:i + 1], inorder[:i]) root.right = self.buildTree(preorder[i + 1:], inorder[i + 1:]) return root ``` 2024/10/18 給定inorder和preorder的array，重新建成tree inorder分法很直觀，preorder只要記得，分配到數字的數量會是一樣的就好 ```python class Solution: def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]: return self.reconstruct(preorder, inorder) def reconstruct(self, preorder, inorder): if not preorder or not inorder: return None root = preorder[0] i = inorder.index(root) left = self.reconstruct(preorder[1:i + 1], inorder[:i]) right = self.reconstruct(preorder[i + 1:], inorder[i + 1:]) return TreeNode(root, left, right) ``` --- ### **優化** 已知Preorder 的第一個 element 會是根，而 Preorder 的問題會是，在後面的 element，不知道有哪些是屬於左子樹，哪些是右子樹，也許全都是左子樹，也可能全部都是右子樹。 這邊可以藉由 Inorder 來判斷。 假設 Preorder 的第一個 element 是 r0，則在 Inorder中，r0 之前的，就是左子樹；r0 之後的，就是右子樹，跟據左子樹跟右子樹的這些 elements，就可以判斷在 Preorder 當中，哪些屬於左子樹，哪些是右子樹。 時間複雜度O(n) ```python class Solution: def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]: # 前序 (preorder): 中 -> 左 -> 右 # 中序 (inorder): 左 -> 中 -> 右 if not preorder or not inorder: return None root = TreeNode() root.val = preorder[0] mid = inorder.index(root.val) root.left = self.buildTree(preorder[1 : mid + 1], inorder[: mid]) root.right = self.buildTree(preorder[mid + 1 : ], inorder[mid + 1:]) return root ``` --- **:warning: 錯誤語法** :::warning 初始化樹點 : TreeNode() ::: **:thumbsup:學習** :::success 前序 (preorder): 中 -> 左 -> 右 中序 (inorder): 左 -> 中 -> 右 後序 (postorder): 左 -> 右 -> 中 List.index( 某東西 ) -> 會回傳其在list中對應的index ::: **思路** **講解連結** Provided by. NeetCode https://medium.com/@cashbooktw/construct-binary-tree-with-preorder-and-inorder-traversal-c50fb945f00f ###### tags: `binary tree` `medium` `leetcode`