由二叉树的层序和中序建树

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

const int maxn = 1000000;

void printVector(vector<int>& vt) {
    int size = vt.size();
    for (int i = 0; i < size; i++) {
        printf("%d", vt[i]);
        if (i != size - 1) printf(" ");
        else printf("\n");
    }
}

struct Node{
    int data;
    Node *lchild, *rchild;
    Node(int v) :data(v), lchild(NULL), rchild(NULL) {}
};

int n;
vector<int> pre, layer, in;
unordered_map<int, int> value_index;

void insert(Node * & root, int data, int index){
    if (root == NULL){
        root = new Node(data);
        return;
    }
    
    int rootIndex = value_index[root->data];
    if (index < rootIndex) insert(root->lchild, data, index);
    else insert(root->rchild, data, index);
}

void preOrder(Node * root){
    if (root == NULL) return;
    pre.push_back(root->data);
    preOrder(root->lchild);
    preOrder(root->rchild);
}

int main(){
    scanf("%d", &n);
    layer.resize(n);
    in.resize(n);

    for (int i = 0; i < n; i++) {
        scanf("%d", &layer[i]);
    }
    for (int i = 0; i < n; i++) {
        
        scanf("%d", &in[i]);
        value_index[in[i]] = i;
    }
    Node * root = NULL;

    for (auto x : layer) {
        int index = value_index[x];
        insert(root, x, index);
    }
    
    preOrder(root);
    printVector(pre);
    
}