【PAT甲级】1066 Root of AVL Tree (25 分)（AVL树建树模板）

题意：

输入一个正整数N（<=20），接着输入N个结点的值，依次插入一颗AVL树，输出最终根结点的值。

AAAAAccepted code：

 #define HAVE_STRUCT_TIMESPEC

 #include<bits/stdc++.h>

 using namespace std;

 int a[];

 typedef struct node{

     int val;

     node*left,*right;

 };

 node*left_rotate(node*root){

     node*tamp=root->right;

     root->right=tamp->left;

     tamp->left=root;

     return tamp;

 }

 node*right_rotate(node*root){

     node*tamp=root->left;

     root->left=tamp->right;

     tamp->right=root;

     return tamp;

 }

 node*left_right(node*root){

     root->left=left_rotate(root->left);

     return right_rotate(root);

 }

 node*right_left(node*root){

     root->right=right_rotate(root->right);

     return left_rotate(root);

 }

 int get_height(node*root){

     if(root==NULL)

         return ;

     return max(get_height(root->left),get_height(root->right))+;

 }

 node*inser(node*root,int val){

     if(root==NULL){

         root=new node();

         root->val=val;

         root->left=root->right=NULL;

     }

     else if(val<root->val){

         root->left=inser(root->left,val);

         if(get_height(root->left)-get_height(root->right)==)

             root=val<root->left->val?right_rotate(root):left_right(root);

     }

     else{

         root->right=inser(root->right,val);

         if(get_height(root->right)-get_height(root->left)==)

             root=val>root->right->val?left_rotate(root):right_left(root);

     }

     return root;

 }

 int main(){

     ios::sync_with_stdio(false);

     cin.tie(NULL);

     cout.tie(NULL);

     int n;

     cin>>n;

     for(int i=;i<=n;++i)

         cin>>a[i];

     node*ans=NULL;

     for(int i=;i<=n;++i)

         ans=inser(ans,a[i]);

     cout<<ans->val;

     return ;

 }