题目

An AVL tree is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node difer by at most one; if at any time they difer by more than one, rebalancing is done to restore this property. Figures 1-4 illustrate the rotation rules.
Now given a sequence of insertions, you are supposed to tell the root of the resulting AVL tree.
Input Specification:
Each input file contains one test case. For each case, the first line contains a positive integer N (≤20) which is the total number of keys to be inserted. Then N distinct integer keys are given in the next line. All the numbers in a line are separated by a space.
Output Specification:
For each test case, print the root of the resulting AVL tree in one line.
Sample Input 1:
5
88 70 61 96 120
Sample Output 1:
70
Sample Input 2:
7
88 70 61 96 120 90 65
Sample Output 2:
88

题目分析

已知平衡二叉树建树序列，求建树后的根节点

解题思路

1.建树（平衡二叉树insert节点）
2.打印根节点

易错点

左旋、右旋、插入节点方法，参数列表中要用指针引用node *&root，否则是值传递，方法中对root本身的修改不会在main函数中生效

Code

#include <iostream>
using namespace std;
struct node {
    int data;
    int heigh=0;
    node * left=NULL;
    node * right=NULL;
    node() {}
    node(int _data):data(_data) {
        heigh=1;
    }
};
int getHeigh(node * root) {
    if(root==NULL)return 0;
    return root->heigh;
}
void updateHeigh(node * root) {
    root->heigh=max(getHeigh(root->left),getHeigh(root->right))+1;
}
void L(node * &root) {
    //左旋
    node * temp=root->right;
    root->right=temp->left;
    temp->left=root;
    updateHeigh(root);
    updateHeigh(temp);
    root=temp;
}
void R(node * &root) {
    //右旋
    node * temp=root->left;
    root->left=temp->right;
    temp->right=root;
    updateHeigh(root);
    updateHeigh(temp);
    root=temp;
}
int getBalanceFactor(node *root) {
    return getHeigh(root->left)-getHeigh(root->right);
}
void insert(node * &root, int val) {
    if(root==NULL) {
        root=new node(val);
        return;
    }
    if(val<root->data) {
        insert(root->left,val);
        updateHeigh(root);
        if(getBalanceFactor(root)==2) {
            if(getBalanceFactor(root->left)==1) {
                //LL
                R(root);
            } else if(getBalanceFactor(root->left)==-1) {
                //LR
                L(root->left);
                R(root);
            }
        }
    } else {
        insert(root->right,val);
        updateHeigh(root);
        if(getBalanceFactor(root)==-2) {
            if(getBalanceFactor(root->right)==-1) {
                //RR
                L(root);
            } else if(getBalanceFactor(root->right)==1) {
                //RL
                R(root->right);
                L(root);
            }
        }
    }
}
int main(int argc,char * argv[]) {
    int n,m;
    scanf("%d",&n);
    node * root=NULL;
    for(int i=0; i<n; i++) {
        scanf("%d",&m);
        insert(root,m);
    }
    printf("%d",root->data);
    return 0;
}

PAT Advanced 1066 Root of AVL Tree (25) [平衡?叉树（AVL树）]

原文：https://www.cnblogs.com/houzm/p/12340293.html