剑指offer（四）：重建二叉树

class Solution {
public:
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        if(pre.size()>0&&vin.size()>0){
            return reConstructBinaryTree2(pre,vin,0,pre.size()-1,0,vin.size()-1);
        }
        return NULL;
    }
    TreeNode* reConstructBinaryTree2(vector<int> pre,vector<int> vin,
                                     int preStart,int preEnd,
                                     int vinStart,int vinEnd){
        if(preStart>preEnd || vinStart>vinEnd )
            return NULL;
        TreeNode* root = new TreeNode(pre[preStart]);
        vector<int>::iterator it = find(vin.begin(),vin.end(),pre[preStart]);
        int mid = &*it-&vin[0];
        int len = mid - vinStart;
        root->left = reConstructBinaryTree2(pre,vin,preStart+1,preStart+len,vinStart,mid-1);
        root->right = reConstructBinaryTree2(pre,vin,preStart+len+1,preEnd,mid+1,vinEnd);
        return root;
    }
};
记得中间变量要写在里面，不能写在递归函数外面

class Solution {
public:
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        if(pre.size()>0&&vin.size()>0){
            return reConstructBinaryTree2(pre,vin,0,pre.size()-1,0,vin.size()-1);
        }
        return NULL;
    }
    TreeNode* reConstructBinaryTree2(vector<int> pre,vector<int> vin,
                                     int preStart,int preEnd,
                                     int vinStart,int vinEnd){
        TreeNode* root = new TreeNode(pre[preStart]);
        if(preStart == preEnd && vinStart == vinEnd && pre[preStart]==vin[vinStart]){
            return root;
        }
        vector<int>::iterator it = find(vin.begin(),vin.end(),pre[preStart]);
        
        int mid = &*it-&vin[0];
        int len = mid - vinStart;
        if(len>0)
            root->left = reConstructBinaryTree2(pre,vin,preStart+1,preStart+len,vinStart,mid-1);
        if(len<preEnd - preStart)
            root->right = reConstructBinaryTree2(pre,vin,preStart+len+1,preEnd,mid+1,vinEnd);
        return root;
    }
};