105. Construct Binary Tree from Preorder and Inorder Traversal“编程题”
2017-11-23 13:51:47         来源：SYSU_xiandan的博客

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:

You may assume that duplicates do not exist in the tree.

Code(LeetCode运行16ms)

```/**
* 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& preorder, vector& inorder) {
return buildTree(preorder.begin(), preorder.end(), inorder.begin(), inorder.end());
}

TreeNode* buildTree(vector::iterator pre_begin, vector::iterator pre_end, vector::iterator in_begin, vector::iterator in_end) {
if (pre_begin == pre_end) {
return NULL;
}
if (in_begin == in_end) {
return NULL;
}

auto root = new TreeNode(*pre_begin);
auto RootPos = find(in_begin, in_end, *pre_begin);
auto leftSize = distance(in_begin, RootPos);

root -> left = buildTree(next(pre_begin), next(pre_begin, leftSize + 1), in_begin, next(in_begin, leftSize));
root -> right = buildTree(next(pre_begin, leftSize + 1), pre_end, next(RootPos), in_end);
return root;
}
};```