solution.md

# 从中序与后序遍历序列构造二叉树

<p>根据一棵树的中序遍历与后序遍历构造二叉树。</p>

<p><strong>注意:</strong><br>
你可以假设树中没有重复的元素。</p>

<p>例如，给出</p>

<pre>中序遍历 inorder =&nbsp;[9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]</pre>

<p>返回如下的二叉树：</p>

<pre>    3
   / \
  9  20
    /  \
   15   7
</pre>


## template

```cpp
#include <bits/stdc++.h>
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<int> &inorder, vector<int> &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<int> &inorder, int i1, int i2, vector<int> &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

```