// 二叉树的中后序构造
int build(int il, int ir, int pl, int pr) {
    int rt=post[pr];
    int k=pos[k];
    if(k>il) l[rt]=build(il, k-1, pl, pl+k-1-il);
    if(k<ir) r[rt]=build(k+1, ir, pl+k-il, pr-1);
    return rt;
}

// 二叉树的中序遍历
void dfs(int u) {
    if(u==-1) return;
    dfs(l[u]);
    cout << u << ' ';
    dfs(r[u]);
}

// 二叉树的层次遍历
void bfs(int u) {
    int hh=0, tt=0;
    q[0]=u;
    while(hh<=tt) {
        int t=q[hh++];
        if(~l[t]) q[++tt]=l[t];
        if(~r[t]) q[++tt]=r[t];
    }
    for(int i=0; i<=tt; i++) cout << q[i];
}

// 反转二叉树
void invert(int u) {
    if(u==-1) return;
    invert(l[u]);
    invert(r[u]);
    swap(l[u], r[u]);
}

// BST的插入
void insert(int &u, int w) {
    if(!u) {
        u=++idx;
        v[u]=w;
    } else if(w<=v[u]) insert(l[u], w);
    else insert(r[u], w);
}