题解 | #重建二叉树#

解法：
使用递归重建左右子树即可。与输出二叉树右视图比较相似。
结束递归的条件为preStart > pre.size()或者vStart > vEnd;
左子树根节点在前序遍历pre中的位置为preStart = preStart + 1，全部左子树位于中序遍历vin[vStart:rootIdx-vin.begin()-1]，其中rootIdx为根节点在中序遍历中的索引。右子树同理。

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        return constructBinaryTree(pre, 0, vin, 0, vin.size());
    }

    TreeNode* constructBinaryTree(vector<int>& pre, int preStart, vector<int>& vin,
                                  int vStart, int vEnd)
    {
        if(preStart >= pre.size()) return NULL;
        if(vStart > vEnd) 
            return NULL;
        TreeNode* root = new TreeNode(pre[preStart]);
        vector<int>::iterator rootIter = find(
            vin.begin()+vStart, vin.begin()+vEnd, pre[preStart]
        );
        TreeNode* leftTree = constructBinaryTree(
            pre, preStart+1, vin, vStart, rootIter - vin.begin() - 1
        );
        TreeNode* rightTree = constructBinaryTree(
            pre, preStart+rootIter-(vin.begin()+vStart)+1, vin, rootIter-vin.begin()+1, vEnd);
        root->left = leftTree;
        root->right = rightTree;
        return root;
    }
};