# 

(2020-02-08) LeetCode 

- [105. ](https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/)
- [106. ](https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/)
- [889. ](https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-postorder-traversal/)



## 105. 

### 

```


:




 preorder =[3,9,20,15,7]
 inorder = [9,3,15,20,7]


    3
   / \
  9  20
    /  \
   15   7
```

### 


![](https://p.ipic.vip/1ir43q.jpg)

`` preorder  val  inorder  inorder  i
`` i i 



![](https://p.ipic.vip/47ywwa.jpg)



![](https://p.ipic.vip/hbznvj.jpg)

 preorder 9

![](https://p.ipic.vip/k7hkj4.jpg)

 preorder 20 1

![](https://p.ipic.vip/8zc2e6.jpg)



![](https://p.ipic.vip/qvjh0a.jpg)

 inorder  preorder 

### 

Python3

Python3 Code:

```python
class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        # inorder  postorder
        if not preorder:
            return None
        root = TreeNode(preorder[0])

        i = inorder.index(root.val)
        root.left = self.buildTree(preorder[1:i + 1], inorder[:i])
        root.right = self.buildTree(preorder[i + 1:], inorder[i+1:])

        return root
```

****

-  inorder  preorder  1 N  $O(N)$ N 
-   N $O(N)$ N 

> 

## 106. 



### 

```


:




 inorder =[9,3,15,20,7]
 postorder = [9,15,7,20,3]


    3
   / \
  9  20
    /  \
   15   7
```

### 


![](https://p.ipic.vip/r78dsl.jpg)

`` postorder  val  inorder  inorder  i
`` i i 



![](https://p.ipic.vip/35n3lv.jpg)



![](https://p.ipic.vip/hbznvj.jpg)

 1 postorder 20

![](https://p.ipic.vip/kyjr7z.jpg)



![](https://p.ipic.vip/qvjh0a.jpg)

 inorder  postorder 

### 

Python3

Python3 Code:

```python
class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
        # inorder  postorder
        if not inorder:
            return None
        root = TreeNode(postorder[-1])
        i = inorder.index(root.val)
        root.left = self.buildTree(inorder[:i], postorder[:i])
        root.right = self.buildTree(inorder[i+1:], postorder[i:-1])

        return root
```

****

-  inorder  postorder  1 N  $O(N)$ N 
-   N $O(N)$ N 

> 

## 889. 

### 

```


prepost





pre = [1,2,4,5,3,6,7], post = [4,5,2,6,7,3,1]
[1,2,3,4,5,6,7]




1  

## 

 1 1



```python
node.left = self.constructFromPrePost(pre[1:i + 2], post[:i + 1])
node.right = self.constructFromPrePost(pre[i + 2:], post[i + 1:-1])

```

 pre pre[1:i + 2] pre[i + 2:] 1 pre  

 post post[:i + 1]  post[i + 1:-1] 1 post 



## 

 LeetCode https://github.com/azl397985856/leetcode   37K star 

 LeetCode 

![](https://p.ipic.vip/vzbaxz.jpg)