https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
/**
* 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:
typedef vector<int>::iterator Iter;
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
return buildTree(inorder.begin(), inorder.end(), preorder.begin(), preorder.end());
}
TreeNode *buildTree(Iter istart, Iter iend, Iter pstart, Iter pend) {
if (istart == iend) {
return nullptr;
}
TreeNode* node = new TreeNode(*pstart);
Iter ipos = find(istart, iend, *pstart);
node->left = buildTree(istart, ipos, pstart+1, pstart+(ipos-istart)+1);
node->right = buildTree(ipos+1, iend, pstart+(ipos-istart)+1, pend);
return node;
}
};
