#### [剑指 Offer 07. 重建二叉树](https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof/)

难度 中等

输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

 

例如，给出

```
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
```

返回如下的二叉树：

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

 

**限制：**

```
0 <= 节点个数 <= 5000
```

#### 解法

```java
class Solution {
    HashMap<Integer, Integer> map = new HashMap<>();
    int[] preorder;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        return helper(0, 0, inorder.length - 1);
    }

    private TreeNode helper(int pre_root, int in_l, int in_r) {
        if (in_l > in_r) return null;
        TreeNode tn = new TreeNode(preorder[pre_root]);
        int i = map.get(preorder[pre_root]);
        tn.left = helper(pre_root + 1, in_l, i - 1);
        tn.right = helper(pre_root + 1 + (i - in_l), i + 1, in_r);
        return tn;
    }
}
```

