题解 | 二叉排序树

#include <bits/stdc++.h>
using namespace std;
const int maxn = 110;
struct node{
    int l,r,v;
}mu[maxn];
int dfs(int s, int va, int id){
    if(va>mu[s].v){
        if(mu[s].r==-1){
            mu[s].r = id;
            mu[id].v = va;
            return s;
        }else  return dfs(mu[s].r, va, id);
    }else{
        if(mu[s].l==-1){
            mu[s].l = id;
            mu[id].v = va;
            return s;
        }else  return dfs(mu[s].l, va, id);
    }
}
vector<int>ans;
int main() {
    int n,va;
    cin>>n;
    int cnt=0;
    for(int i=1; i<=n; i++) {
        mu[i].l = -1;
        mu[i].r = -1;
    }  
    for(int i=1; i<=n; i++){
        cin>>va;
        if(i == 1){
            ans.push_back(-1);
            mu[i].v=va;
        }else{
            int y = dfs(1, va, i);
            ans.push_back(mu[y].v);
        }
    }
    for(auto it:ans)  cout<<it<<endl;
    return 0;
}
// 64 位输出请用 printf("%lld")