# 从前序与中序遍历序列构造二叉树
给定一棵树的前序遍历 preorder 与中序遍历 inorder。请构造二叉树并返回其根节点。
示例 1:
Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]
示例 2:
Input: preorder = [-1], inorder = [-1]
Output: [-1]
提示:
1 <= preorder.length <= 3000inorder.length == preorder.length-3000 <= preorder[i], inorder[i] <= 3000preorder 和 inorder 均无重复元素inorder 均出现在 preorderpreorder 保证为二叉树的前序遍历序列inorder 保证为二叉树的中序遍历序列
## template
```cpp
#include
using namespace std;
struct TreeNode
{
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution
{
private:
unordered_map inMap;
public:
TreeNode *myBuildTree(vector &preorder, int preStart, int preEnd, vector &inorder, int inStart, int inEnd)
{
if (preStart > preEnd)
return nullptr;
TreeNode *root = new TreeNode(preorder[preStart]);
int inRoot = inMap[preorder[preStart]];
int numsLeft = inRoot - inStart;
root->left = myBuildTree(preorder, preStart + 1, preStart + numsLeft, inorder, inStart, inRoot - 1);
root->right = myBuildTree(preorder, preStart + numsLeft + 1, preEnd, inorder, inRoot + 1, inEnd);
return root;
}
TreeNode *buildTree(vector &preorder, vector &inorder)
{
int n = preorder.size();
for (int i = 0; i < n; i++)
{
inMap[inorder[i]] = i;
}
return myBuildTree(preorder, 0, n - 1, inorder, 0, n - 1);
}
};
```
## 答案
```cpp
```
## 选项
### A
```cpp
```
### B
```cpp
```
### C
```cpp
```