# [leetcode] 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.

```//preorder储存数字信息
//inorder存储结构信息
//每次inorder都会把数平分成两半
//注意不要内存超界。
/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
return _buildTree(preorder.begin(), preorder.end(), inorder.begin(), inorder.end());
}
TreeNode * _buildTree(vector<int>::iterator preorderBegin, vector<int>::iterator preorderEnd, vector<int>::iterator inorderBegin, vector<int>::iterator inorderEnd){
if(preorderBegin == preorderEnd){
return NULL;
}
int val = *preorderBegin;
TreeNode* p = new TreeNode(val);
size_t i;
for(i = 0; inorderBegin + i != inorderEnd; i++){
if(*(inorderBegin + i) == val){
break;
}
}
p->left = _buildTree(preorderBegin + 1, preorderBegin + i + 1, inorderBegin, inorderBegin + i);
p->right = _buildTree(preorderBegin + 1 + i, preorderEnd, inorderBegin + i + 1, inorderEnd);
return p;
}
};```

This site uses Akismet to reduce spam. Learn how your comment data is processed.