题解 | 二叉排序树

#include <iostream>
using namespace std;
typedef struct btree{
  struct btree *left;
  struct btree *right;
  int data;
}btree;
int ans;
btree *insert(btree *t,int x)
{
   if(t==NULL)
   {
    t=new btree;
    t->left=t->right=NULL;
    t->data=x;
    ans=-1;
   }
   if(x>t->data)
   {
     int f=(t->right==NULL);
     t->right=insert(t->right,x);
     if(f&&t->right!=NULL)
     ans=t->data;
   }
   if(x<t->data)
   {
     int f=(t->left==NULL);
     t->left=insert(t->left,x);
     if(f&&t->left!=NULL)
     ans=t->data;
   }
   return t;
}
int main() {
  int n;cin>>n;
   btree *t=NULL;
  while(n--)
  {
    int x;cin>>x;
    t=insert(t,x);
    cout<<ans<<endl;
  }
}