1066 Root of AVL Tree [重要 待分析 天勤] 算法下P325 平衡二叉树

//1066 Root of AVL Tree [重要 待分析  天勤] 算法下P325 平衡二叉树
#include <iostream>
using namespace std;
typedef struct BTNode{
    int data;
    struct BTNode *lChild,*rChild;
}BTNode;//C C++ 通用定义方式

BTNode* rotateL(BTNode *root){
    BTNode *t = root->rChild;
    root->rChild = t->lChild;
    t->lChild = root;
    return t;
}

BTNode* rotateR(BTNode *root){
    BTNode *t = root->lChild;
    root->lChild = t->rChild;
    t->rChild = root;
    return t;
}

BTNode *rotateLR(BTNode *root){
    root->lChild = rotateL(root->lChild);
    return rotateR(root);
}
BTNode* rotateRL(BTNode *root){
    root->rChild = rotateR(root->rChild);
    return rotateL(root);
}
int getHeight(BTNode *root){
    if(root == NULL) return 0;
    return max(getHeight(root->lChild),getHeight(root->rChild))+1;
}

void insert(BTNode *&root,int data){
    if(root == NULL){
        root = new BTNode();
        root->data = data;
        root->lChild = root->rChild = NULL;
    }else if(data < root->data){
        insert(root->lChild,data);
        if(getHeight(root->lChild) - getHeight(root->rChild) == 2){
            root = data < root->lChild->data ? rotateR(root) : rotateLR(root);
        }
    }else{ //相等的情况呢？？
        insert(root->rChild,data);
        if(getHeight(root->lChild) - getHeight(root->rChild) == -2){
            root = data > root->rChild->data ? rotateL(root) : rotateRL(root);
        }
    }
}


int main(){
    int N,data;
    cin>>N;
    BTNode *root = NULL;
    for(int i=0;i<N;++i){
        cin>>data;
        insert(root,data);
    }
    cout<<root->data;
    return 0;
}