# 106. Construct Binary Tree from Inorder and Postorder Traversal

106Construct Binary Tree from Inorder and Postorder Traversal

Given two integer arrays `inorder` and `postorder` where `inorder` is the inorder traversal of a binary tree and `postorder` is the postorder traversal of the same tree, construct and return the binary tree.

Example 1:

```Input: inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
Output: [3,9,20,null,null,15,7]
```

Example 2:

```Input: inorder = [-1], postorder = [-1]
Output: [-1]
```

Constraints:

• `1 <= inorder.length <= 3000`
• `postorder.length == inorder.length`
• `-3000 <= inorder[i], postorder[i] <= 3000`
• `inorder` and `postorder` consist of unique values.
• Each value of `postorder` also appears in `inorder`.
• `inorder` is guaranteed to be the inorder traversal of the tree.
• `postorder` is guaranteed to be the postorder traversal of the tree.

### The solution to the above question

/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode() : val(0), left(nullptr), right(nullptr) {}
*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* helper(vector<int>&invector<int>& postint insint ineint posint poe){
if(ins>ine){
return NULL;
}
int idx=0;
for(int i=insi<=inei++){
if(in[i]==post[poe]){
idx=i;
break;
}
}
int inls=ins;
int inrs=idx+1;
int inle=idx-1;
int inre=ine;
int pls=pos;
int pre=poe-1;
int ple=pls+inle-inls;
int prs=ple+1;

TreeNode* root=new TreeNode(post[poe]);
root->left=helper(in,postinlsinleplsple);
root->right=helper(inpostinrsinreprspre);

return root;

}

TreeNode* buildTree(vector<int>& inordervector<int>& postorder) {
return helper(inorder,postorder,0,inorder.size()-1,0,postorder.size()-1);
}
};