leetcode 105. 从前序与中序遍历序列构造二叉树

递归，
在中序中找前序的第一个元素，
之后切割成两个相同子问题

class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if(preorder.size()==0){
            return nullptr;
        }
        TreeNode * root = new TreeNode(preorder[0]);
        vector<int>::iterator in_mid = find(begin(inorder), end(inorder), root->val);
        vector<int>::iterator pr_mid = next(begin(preorder),  1 + in_mid - begin(inorder));
        vector<int> leftpre = vector<int>(next(begin(preorder)), pr_mid);
        vector<int> leftord = vector<int>(begin(inorder), in_mid);

        root->left = buildTree( leftpre, leftord );

        vector<int> rightpre = vector<int>(pr_mid, end(preorder));
        vector<int> rightord = vector<int>(next(in_mid), end(inorder));

        root->right = buildTree(rightpre,rightord);
        return root;
    }
};