数据结构day44

总结：今天时间不多，先不做复习题了；

题目详情 - 1043 Is It a Binary Search Tree (pintia.cn)

思路：首先假设是BST，用序列分别建立BST和MIRROR_BST树，和先序比较，一样就yes，不然no； 对比一下答案的思路，用vector比较是否一样更简洁；

#include<iostream>
#include<cmath>
#include<vector>
#include<algorithm>
#pragma warning(disable:4996)
using namespace std;
 
struct node {
	int data;
	node* left;
	node* right;
};
vector<int>original, pre, preM, res;
void insert(node*& root, int data) {
	if (root == NULL) {
		root = new node;
		root->data = data;
		root->left = root->right = NULL;
	}
	else if (root->data > data) {
		insert(root->left, data);
	}
	else
	{
		insert(root->right, data);
	}
}
void pre_traverse(node* root,vector<int>&v,int flag) {//flag==1 is BSI, 0 is mirror
	if (root == NULL) {
		return;
	}
	v.push_back(root->data);
	if (flag) {
		pre_traverse(root->left, v, flag);
		pre_traverse(root->right, v, flag);
	}
	else
	{
		pre_traverse(root->right, v, flag);
		pre_traverse(root->left, v, flag);
	}
 
}
void post_traverse(node* root, vector<int>& v,int flag) {
	if (root == NULL) {
		return;
	}
	if (flag) {
		if (root->left) {
			post_traverse(root->left, v,flag);
		}
		if (root->right) {
			post_traverse(root->right, v,flag);
		}
		v.push_back(root->data);//直接打印也可以
	}
	else
	{
		if (root->right) {
			post_traverse(root->right, v, flag);
		}
		if (root->left) {
			post_traverse(root->left, v, flag);
		}
		v.push_back(root->data);//直接打印也可以
	}
}
int main() {
	node* root = NULL;
	int n, data;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> data;
		original.push_back(data);
		insert(root, data);
	}
	pre_traverse(root, pre, 1);
	pre_traverse(root, preM, 0);
	if (original == pre) {
		cout << "YES\n";
		post_traverse(root, res,1);
		for (int i = 0; i < res.size(); i++) {
			if (i != 0) {
				cout << ' ';
			}
			cout << res[i];
		}
	}
	else if (original == preM) {
		cout << "YES\n";
		post_traverse(root, res,0);
		for (int i = 0; i < res.size(); i++) {
			if (i != 0) {
				cout << ' ';
			}
			cout << res[i];
		}
	}
	else
	{
		cout << "NO\n";
	}
 
	return 0;
}

题目详情 - 1064 Complete Binary Search Tree (pintia.cn) 

思路：理解了接近一小时，给定序列，排序后可知树的中序遍历，然后因为是完全二叉树，所以已知每个节点的位置；最后在递归，在比节点小的放在2*i位置，节点在i，比节点大的放在2*i+1位置；希望下次写有新的理解，还有需要复习中序和三种其他遍历建树的写法；

#include<iostream>
using namespace std;
#include<algorithm>
 
int arr[1001], res[1001], n, index;
void in_traverse(int root) {
	if (root > n) {
		return;
	}
	in_traverse(2 * root);//root从1开始
	res[root] = arr[index++];//找位置，从小到大
	in_traverse(2 * root + 1);
}
int main()
{
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	sort(arr, arr + n);//in_order traverse
	in_traverse(1);
	for (int i = 1; i <= n; i++) {
		if (i != 1) {
			cout << " ";
		}
		cout << res[i];
	}
 
 
	return 0;
}