题解 | #重建二叉树#

思路：利用前序中序遍历的性质，首先在前序中找到根节点，那么在中序遍历中，根节点的左边一定是他的左子树，右边是右子树，然后根据这个特点，对左和右子树继续进行递归

TreeNode* reConBTree(vector<int> pre,int preleft,int preright,vector<int> vin,int vinleft,int vinright)
    {
        /*
        pre为前序序列，vin为中序序列
        preleft为前序序列左边界，preright为前序序列右边界
        vinleft为中序序列左边界，vinright为中序序列右边界
        */
        //如果左边界>右边界，说明没有子树了，返回空指针
        if(preleft > preright || vinleft > vinright)
        {
            return nullptr;
        }
        //前序序列的第一个元素必定为根节点
        int preroot = pre[preleft];
        int vinroot = vinleft;
        //找到根节点在中序序列中的位置
        while(vin[vinroot] != preroot)
            vinroot++;
        //构建根节点
        TreeNode* s = new TreeNode(preroot);
        //左子树的结点数目，即中序序列中根节点到左边界的距离
        int distance = vinroot-vinleft;
        //左子树的所有结点在前序序列中的位置[preleft+1,preleft+distance]
        //左子树的所有结点在中序序列中的位置[vinleft,vinroot-1]
        s->left = reConBTree(pre, preleft+1,preleft+distance, vin, vinleft, vinroot-1);
        //右子树的所有结点在前序序列中的位置[preleft+distance+1,preright]
        //右子树的所有结点在中序序列中的位置[vinroot+1,vinright]
        s->right = reConBTree(pre, preleft+distance+1, preright, vin, vinroot+1, vinright);
        return s;
    }
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        return reConBTree(pre, 0, pre.size()-1, vin, 0, vin.size());
    }

TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        int n = pre.size();
        int m = vin.size();
        //如果为0，说明没有子树了
        if(n == 0 || m == 0)
            return nullptr;
        //构建根节点
        TreeNode *root = new TreeNode(pre[0]);
        for(int i = 0;i<vin.size();++i)
        {
            //找到中序遍历中的前序第一个元素
            if(pre[0] == vin[i])
            {
                //左子树的前序遍历序列
                vector<int> leftpre(pre.begin()+1,pre.begin()+i+1);
                //左子树的中序遍历序列
                vector<int> leftvin(vin.begin(),vin.begin()+i);
                //构建左子树
                root->left = reConstructBinaryTree(leftpre,leftvin);
                //右子树的前序遍历序列
                vector<int> rightpre(pre.begin()+i+1,pre.end());
                //右子树的中序遍历序列
                vector<int> rightvin(vin.begin()+i+1,vin.end());
                //构建右子树
                root->right = reConstructBinaryTree(rightpre,rightvin);
                break;
            }
        }
        return root;
    }