题解 | #重构树#

树重构，第一时间想到递归，既然要用到递归，必然要确定根，左子树和右子树，可以根据给定的前序遍历和中序遍历序列获得。
这里注意两点：1、每次递归若都用一个vector的话，空间消耗大，改为传递子数组的上下界；2、子数组上下界确定，依赖于根节点确定，千万不能根据根节点的下标确定上下界，可以根据根节点下标推算，子数组元素个数。

class Solution {
public:
    TreeNode* easyConstruct(vector<int> pre, int pre_left, int pre_right,vector<int> vin,int vin_left,int vin_right){
        TreeNode* head = new TreeNode(pre[pre_left]);
        int l = pre.size();
        int gen;
        if(pre_left > pre_right) return NULL;
        for(int i=vin_left;i<vin_right;i++){
            if(vin[i] == pre[pre_left]){
                gen = i;
                break;
            }
        }
        head->left = easyConstruct(pre, pre_left+1, pre_left+gen-vin_left, vin, vin_left, gen-1);
        head->right = easyConstruct(pre, pre_left+gen-vin_left+1, pre_right, vin, gen+1, vin_right);
        return head;
    }
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        if(pre.size() == 0) return NULL;
        int l = pre.size();
        return easyConstruct(pre, 0 , l-1, vin, 0 , l-1);
    }
};