[C++知识库]PAT甲级 1066（C++）

对二叉树不太熟悉，看了这个大佬的代码：1066. Root of AVL Tree (25)-PAT甲级真题_柳婼 の blog-CSDN博客

然后依葫芦画瓢写了一遍，里面用了很多递归，对指针的使用也要慎重思考（要不要用引用之类的……），相关的练的多了，应该就不用再花这么多时间考虑了。这题以后还要再看看，重新写写。

#include<iostream>
using namespace std;
struct node {
	int e;
	node* left;
	node* right;
};
node* LL(node * root) {
	node* t = root->left;
	root->left = t->right;
	t->right = root;
	return t;
}
node* RR(node* root) {
	node* t = root->right;
	root->right = t->left;
	t->left = root;
	return t;
}
node* LR(node* root) {
	root->left = RR(root->left);
	return LL(root);
}
node* RL(node* root) {
	root->right = LL(root->right);
	return RR(root);
}
int getHeight(node* root) {
	if (root == NULL) return 0;
	else return max(getHeight(root->left), getHeight(root->right))+1;
}
node* insert(node* root, int e) {
	if (root == NULL) {
		root = new node;
		root->e = e;
		root->left = root->right = NULL;
	}
	else if (root->e > e) {
		root->left = insert(root->left, e);
		if (getHeight(root->left) - getHeight(root->right) == 2) {
			if (root->left->e > e) root = LL(root);
			else root = LR(root);
		}
	}
	else {
		root->right = insert(root->right, e);
		if (getHeight(root->right) - getHeight(root->left) == 2) {
			if (root->right->e <= e) root= RR(root);
			else root= RL(root);
		}
	}
	return root;
}
int main() {
	int N; cin >> N;
	node* root = NULL;
	for (int i = 1; i <= N; i++) {
		int e; cin >> e;
		root = insert(root, e);
	}
	cout << root->e;
	return 0;
}