剑指offer----重建二叉树

题目描述

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

//get_vec返回一个根据索引分割的数组，包括vec[begin]和vec[end]。
vector<int> get_vec(vector<int>&vec,int begin,int end)
    {
        vector<int> res;
        for(int i=begin;i>=&&i<=end;++i)//begin可能大于end也可能小于 
                                         //0，此时应该返回空数组
        {
            res.push_back(vec[i]);
        }
        return res;
    }
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        if(pre.size()==)return NULL;//子树为空，返回NULL
        TreeNode* root=new TreeNode(pre[]);
        int root_int_vin=;
        while(pre[]!=vin[root_int_vin])
        {
            root_int_vin++;//寻找根在中序遍历中的位置，
                           //很明显，根的左边为左子树，右边为右子树
        }
        /*
        不管是前序遍历或者中序遍历，右子树始终是在最后访问的，
        所以可以分割出来根，左子树右子树。
        {1,2,4,7,3,5,6,8},根为1,左子树{2,4,7},右子树{3，5，6，8}。
        {4,7,2,1,5,3,8,6}，左子树{4,7,2},根为1,右子树{5,3,8,6}。
        */

        //递归调用,从上到下建立二叉树
        root->left=reConstructBinaryTree(get_vec(pre,,root_int_vin),get_vec(vin,,root_int_vin-));
        root->right=reConstructBinaryTree(get_vec(pre,root_int_vin+,pre.size()-),get_vec(vin,root_int_vin+,pre.size()-));
        return root;
    }