# 从中序与后序遍历序列构造二叉树
根据一棵树的中序遍历与后序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。
例如，给出
中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]
返回如下的二叉树：
3
/ \
9 20
/ \
15 7
## 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
{
public:
TreeNode *buildTree(vector &inorder, vector &postorder)
{
if (0 == inorder.size() || 0 == postorder.size())
{
return NULL;
}
return build(inorder, 0, inorder.size() - 1, postorder, 0, postorder.size() - 1);
}
TreeNode *build(vector &inorder, int i1, int i2, vector &postorder, int p1, int p2)
{
TreeNode *root = new TreeNode(postorder[p2]);
int i = i1;
while (i <= i2 && postorder[p2] != inorder[i])
{
i++;
}
int left = i - i1;
int right = i2 - i;
if (left > 0)
{
root->left = build(inorder, i1, i - 1, postorder, p1, p1 + left - 1);
}
if (right > 0)
{
root->right = build(inorder, i + 1, i2, postorder, p1 + left, p2 - 1);
}
return root;
}
};
```
## 答案
```cpp
```
## 选项
### A
```cpp
```
### B
```cpp
```
### C
```cpp
```