## Construct Binary Tree from Preorder and Inorder Traversal

Given preorder and inorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.

### Analysis:

The idea is similar to the previous question. Just be careful with the order of dividing the vector, and the order of preorder root.

### Code(C++):

/**
* Definition for binary tree
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int findId(int n, vector<int> &inorder){
for (int i=0;i<inorder.size();i++){
if (inorder[i] == n) return i;
}
}

TreeNode* bst(vector<int> &preorder, int &mid, vector<int> &inorder, int st, int ed){
if (st>ed || preorder.size()==mid){
return NULL;
}
TreeNode* root = new TreeNode(preorder[mid]);
int idx = findId(preorder[mid], inorder);
mid++;
root->left = bst(preorder, mid, inorder, st, idx-1);
root->right = bst(preorder, mid, inorder, idx+1, ed);
return root;
}

TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
int mid = 0;
return bst(preorder, mid, inorder, 0, inorder.size());
}
};


### Code(Python):

# Definition for a  binary tree node
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
# @param preorder, a list of integers
# @param inorder, a list of integers
# @return a tree node
def bst(self, preorder, inorder):
if len(preorder) == 0 or len(inorder) == 0:
return None
root = TreeNode(preorder[0])
idx = inorder.index(preorder[0])
preorder.pop(0)
root.left = self.bst(preorder, inorder[0:idx])
root.right = self.bst(preorder, inorder[idx+1:])
return root

def buildTree(self, preorder, inorder):
return self.bst(preorder, inorder)