---
# System prepended metadata

title: '**Leetcode筆記(Construct Binary Tree from Preorder and Inorder Traversal)**'
tags: [medium, binary tree, leetcode]

---

# **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`