PAT甲级1066. Root of AVL Tree PAT甲级1066. Root of AVL Tree

题意：

构造AVL树，返回root点val。

思路：

了解AVL树的基本性质。
AVL树

ac代码：

C++

// pat1066.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"

#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<queue>
#include<vector>
#include<cstring>
#include<stdio.h>
#include<map>
#include<cmath>
#include<unordered_map>

using namespace std;

struct AvlNode
{
	int data;
	AvlNode* left;
	AvlNode* right;
	int height;
	AvlNode(int x) : data(x), left(NULL), right(NULL), height(0) {}
};

int height(AvlNode* root)
{
	return root == NULL ? -1 : root->height;
}

void LLRotate(AvlNode*& root)        //右单
{
	AvlNode* temp = root->left;
	root->left = temp->right;
	temp->right = root;

	temp->height = max(height(temp->left), height(temp->right)) + 1;
	root->height = max(height(root->left), height(root->right)) + 1;

	root = temp;
}

void RRRotate(AvlNode*& root)          //左单
{
	AvlNode* temp = root->right;
	root->right = temp->left;
	temp->left = root;

	temp->height = max(height(temp->left), height(temp->right)) + 1;
	root->height = max(height(root->left), height(root->right)) + 1;

	root = temp;
}

void RLRotate(AvlNode*& root)
{
	LLRotate(root->right);

	RRRotate(root);
}

void LRRotate(AvlNode*& root)
{
	RRRotate(root->left);

	LLRotate(root);
}

void insert(const int& x, AvlNode*& root)
{
	if (!root)
	{
		root = new AvlNode(x);
	}
	else if (x < root->data)
	{
		insert(x, root->left);
		if (height(root->left) - height(root->right) == 2)
		{
			if (x < root->left->data) LLRotate(root);
			else LRRotate(root);
		}
	}
	else if (x > root->data)
	{
		insert(x, root->right);
		if (height(root->right) - height(root->left) == 2)
		{
			if (x > root->right->data) RRRotate(root);
			else RLRotate(root);
		}
	}

	root->height = max(height(root->left), height(root->right)) + 1;
}

int main()
{
	AvlNode* root = NULL;
	int N;
	int i;
	int num[22];

	scanf("%d", &N);

	for (int i = 0; i < N; i++)
	{
		scanf("%d", &(num[i]));
	}

	for (int i = 0; i < N; i++)
	{
		insert(num[i], root);
	}

	printf("%d", root->data);
    return 0;
}