4、重建二叉树

题目：

输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。

例如前序遍历序列和中序遍历序列为{1,2,4,7,3,5,6,8}和{4,7,2,1,5,3,8,6}，假设结果中无重复的数字。重建二叉树并返回

解法：

1、前序遍历二叉树的形式为（根节点，左子树，右子树），中序遍历二叉树的形式为（左子树，根节点，右子树），因此我们需要把前序遍历的第一个结果new一个TreeNode 出来，并在中序遍历中求得根节点对应的index；

2、利用两个循环分别构建左子树的前序结果，中序结果。右子树的前序结果中序结果。利用递归完成题目要求。

代码如下:

TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        if(pre.empty() || vin.empty()|| pre.size()!= vin.size())
            return NULL;
        int n = pre.size();
        int index ;
        TreeNode* root = new TreeNode(pre[0]); //构建根节点
        //root->val = pre[0];
        for(int i = 0;i<n;i++)
        {
            if(vin[i]==pre[0])
            {
                index = i;
                break;
            }
        }
        vector<int> preleft,preright,vinleft,vinright;
        for(int i = 0;i<index;i++) //构建左右子树的遍历序列
        {
            preleft.push_back(pre[i+1]);
            vinleft.push_back(vin[i]);
        }
        for(int i =index+1;i<n;i++)
        {
            preright.push_back(pre[i]);
            vinright.push_back(vin[i]);
        }
        root->left = reConstructBinaryTree(preleft,vinleft);
        root->right = reConstructBinaryTree(preright,vinright);
        return root;
    }