# 105. Construct Binary Tree from Preorder and Inorder Traversal

{% embed url="<https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/>" %}

理解`inorder`traversal list的一个性质：

> 当前`node`左子树的元素一定在它的左边，右子树的元素一定在它右边

遍历`preorder`中的元素：

1. 针对每个元素`node`，都在`inorder`中找下位置`idx`
2. 然后`idx`左边就是node left subtree 的 `inorder`，右边就是right subtree 的`inorder`

递归完成这个遍历，过程中 `preorder`的首个元素会被不断地 pop 出来。

### 01/17/2021 Update:

1. preorder 先序遍历的第一个节点即为根节点。
2. 以根节点来裁切 inorder，会发现两边的 subarray 分别是根节点左右子树的 inorder。

第二点其实要依靠题目里这个提示才能得出：

> You may assume that duplicates do not exist in the tree.

递归直到 inorder 中没元素了（即当前节点不再有children）结束。

```python
class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        if not preorder or not inorder: return None
        
        # 把第一个元素pop出来
        rootVal = preorder.pop(0)
        root = TreeNode(rootVal)
        idx = inorder.index(rootVal)
        
        # 这个写法需要做切片，有点慢，其实可以传递index规避切片，不过这样也能submit，就不改了
        root.left = self.buildTree(preorder, inorder[:idx])
        root.right = self.buildTree(preorder, inorder[idx+1:])

        return root
```
