题解 | #重建二叉树#

看题目首先确定采用分治的思想，通过题目给出的先序遍历与中序遍历确定头结点，然后通过该头结点得到两个子树的先序遍历与中序遍历，重复该过程，最后就可以得到完整的树。
具体实现中采用递归的方法，递归的最大栈深度为n，在递归中有一步需要循环来查找头节点，平均时间复杂度为O(logn)，故该方法时间复杂度为O(nlogn),相较于题目要求的O(n)较差，说明仍有改进空间。
空间复杂度方便，仅在递归时借用了辅助栈，故空间复杂度为O(logn)，满足题目要求。
这里有个技巧是通过迭代器来截断vector，这里迭代器的使用并不像直接使用下标，用起来有一些坑需要注意。vector.begin()指向下标为0的元素，vector.end()指向数组最后的元素。在截断时需要通过begin()与end来构造const_iterator，再通过const_iterator来初始化vector数组。这里就可以根据想要截断的部分距离数组头部与数组尾部的偏移量来人为截断数组。如：

//vector={0,1,2,3,4,5,6,7,8,9}
vector<int>::const_iterator it1 = vector.begin() + 3;
vector<int>::const_iterator it2 = vector.end() - 2;
vector<int> result(it1,it2);
//result={3,4,5,6,7}

如结果所示，上述代码则会截出从距离数组头3个元素开始，到距离数组尾部2个元素结束的子数组。

下面附完整代码。

/**
 * 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) {
        TreeNode* root = nullptr;
        if(pre.size() == 0){
            return root;
        }
        create(root, pre, vin);
        return root;
    }
    void create(TreeNode* &root, vector<int> pre, vector<int> vin){
        root = new TreeNode(pre.at(0));
        int i = 0;
        for(i;i < vin.size();i++){
            if(vin.at(i) == pre.at(0)){
                break;
            }
        }
        if(i > 0){
            vector<int>::const_iterator pb1 = pre.begin() + 1;
            vector<int>::const_iterator pe1 = pre.begin() + i + 1;
            vector<int> pre1(pb1,pe1);
            vector<int>::const_iterator vb1 = vin.begin();
            vector<int>::const_iterator ve1 = vin.begin() + i;
            vector<int> vin1(vb1,ve1);
            create(root->left, pre1, vin1);
        }
        if(i < vin.size() - 1){
            vector<int>::const_iterator pb2 = pre.end() - pre.size() + i + 1;
            vector<int>::const_iterator pe2 = pre.end();
            vector<int> pre2(pb2,pe2);
            vector<int>::const_iterator vb2 = vin.end() - vin.size() + i + 1;
            vector<int>::const_iterator ve2 = vin.end();
            vector<int> vin2(vb2,ve2);
            create(root->right, pre2, vin2);
        }
    }
};