数据结构利用先序和中序实现二叉树的还原

二叉树的还原可以通过先序和中序遍历序列来实现。具体步骤如下：

1. 选取先序遍历序列的第一个元素作为根节点。
2. 在中序遍历序列中找到根节点的位置，将中序遍历序列分为左子树和右子树两部分。
3. 用左子树的元素个数更新先序遍历序列和中序遍历序列，分别得到左子树的先序遍历序列和中序遍历序列，右子树的先序遍历序列和中序遍历序列。
4. 分别对左子树和右子树递归执行1-3步骤，得到左子树和右子树的二叉树。
5. 将根节点与左右子树连接起来，得到整棵二叉树。

下面是一个C++的实现代码示例：

#include<iostream>
#include<vector>
using namespace std;

struct TreeNode{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x):val(x),left(nullptr),right(nullptr){}
};

TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    if(preorder.empty() || inorder.empty() || preorder.size()!=inorder.size()) return nullptr;
    int n = preorder.size();
    return build(preorder, inorder, 0, n-1, 0, n-1);
}

TreeNode* build(vector<int>& preorder, vector<int>& inorder, int pl, int pr, int il, int ir){
    if(pl>pr || il>ir) return nullptr;
    TreeNode* root = new TreeNode(preorder[pl]);
    int k;
    for(k=il;k<=ir;k++){
        if(inorder[k]==preorder[pl]) break;
    }
    int leftcnt = k-il;
    root->left = build(preorder, inorder, pl+1, pl+leftcnt, il, k-1);
    root->right = build(preorder, inorder, pl+leftcnt+1, pr, k+1, ir);
    return root;
}

void preorderTraversal(TreeNode* root){
    if(!root) return;
    cout<<root->val<<" ";
    preorderTraversal(root->left);
    preorderTraversal(root->right);
}

void inorderTraversal(TreeNode* root){
    if(!root) return;
    inorderTraversal(root->left);
    cout<<root->val<<" ";
    inorderTraversal(root->right);
}

int main(){
    vector<int> preorder = {3,9,20,15,7};
    vector<int> inorder = {9,3,15,20,7};
    TreeNode* root = buildTree(preorder, inorder);
    cout<<"preorder: ";
    preorderTraversal(root);
    cout<<endl;
    cout<<"inorder: ";
    inorderTraversal(root);
    cout<<endl;
    return 0;
}

运行结果：

preorder: 3 9 20 15 7 
inorder: 9 3 15 20 7 

可以看到，根据先序遍历序列和中序遍历序列，成功还原了二叉树。