二叉树已知先序和中序或者后序和中序求构造数（这个算法特别神奇）

#include<iostream>
#include<cstring>
#include<cstdio>
#include<map>
#include<vector>
#include<algorithm>
using namespace std;

struct Node
{
    int val;
    Node* left;
    Node* right;
    Node(){left = right=NULL;}
};
map<int,int> valtoid;
Node* Insert(Node* node,int val)
{
    if(node==NULL)
    {
        node = new Node();
        node->val = val;
    }
    else if(valtoid[val]<valtoid[node->val])
        node->left = Insert(node->left,val);
    else
        node->right = Insert(node->right,val);
    return node;
}
void pre_travel(Node* node)
{
    if(NULL==node) return;
    printf("%d ",node->val);
    pre_travel(node->left);
    pre_travel(node->right);
}
void post_travel(Node* node)
{
    if(NULL==node) return;
    post_travel(node->left);
    post_travel(node->right);
    printf("%d ",node->val);
}
int main()
{
    int n;
    scanf("%d",&n); //输入个数
    vector<int> vn;     //先序或者后序
    for(int i=0;i<n;++i)
    {
        int val;
        scanf("%d",&val);
        vn.push_back(val);
    }
    //reverse(vn.begin(),vn.end());  //如果是后序，就反转
    for(int i=0;i<n;++i)    //输入中序
    {
        int a;
        scanf("%d",&a);
        valtoid[a] = i;
    }
    Node* root = NULL;
    cout<<"先序：";
    for(int i=0;i<n;++i) root = Insert(root,vn[i]);
    pre_travel(root);
    puts("");
    cout<<"后序：";
    post_travel(root);
    puts("");
}
/*
//后序，中序
11
7 6 3 5 20 4 24 21 10 1 9
7 6 5 3 9 4 20 1 10 24 21
//先序，中序
11
9 5 6 7 3 1 4 20 10 21 24
7 6 5 3 9 4 20 1 10 24 21
*/