进阶实验4-3.4 笛卡尔树(PTA)（二叉搜索树的判断 + 最小堆(优先队列)的判断 ）

原题链接

#include
#include
#include
#include
using namespace std;
const int MAX = 1e3 + 1;
bool vis[MAX];
vector<int>Q;
struct Tree {
	int k1, k2;
	int l, r;
	Tree(int a, int b, int c, int d) { k1 = a; k2 = b; l = c; r = d; }
	Tree() { k1 = 0; k2 = 0; l = -1; r = -1; }
}T[MAX];
bool Find(int k2,int s) {
	if (s == -1)
		return true;
	else if (T[s].k2 <= k2)
		return false;
		bool f1=Find(T[s].k2, T[s].l);
		Q.push_back(T[s].k1);
		bool f2=Find(T[s].k2, T[s].r);
		return (f1 && f2);
}
bool isyx() {//二叉搜索树的中序遍历的key值是从小到大的
	int j = Q.size(),i;
	for (i = 1; i < j; i++) {
		if (Q[i] <= Q[i - 1])
			break;
	}
	return i == j;
}
int main() {
	int n,i;
	int a, b, c, d;
	scanf("%d", &n);
	for (i = 0; i < n; i++) {
		scanf("%d%d%d%d", &a, &b, &c, &d);
		T[i] = Tree(a, b, c, d);
		if (c != -1)//将读入的根节点的左右子树作访问过的标记，若在vis中没有被标记过,说明该节点是根节点
			vis[c] = true;
		if (d != -1)
			vis[d] = true;
	}
	for ( i = 0; i < n; i++)
		if (!vis[i])
			break;
	int h = i;
	if (Find(T[h].k2-1, h)&&isyx())
		printf("YES\n");
	else
		printf("NO\n");
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

1. 二叉搜索树的判断

因为二叉搜索树的定义是，根节点的左孩子小于根节点，根节点的右孩子大于根节点
所以得到 二叉搜索树的 中序遍历 得到的排序 一定是从小到大
所以判断二叉搜索树只需要 中序遍历后，判断数值是否从小到大

		bool f1=Find(T[s].k2, T[s].l);
		Q.push_back(T[s].k1);
		bool f2=Find(T[s].k2, T[s].r);

bool isyx() {//二叉搜索树的中序遍历的key值是从小到大的
	int j = Q.size(),i;
	for (i = 1; i < j; i++) {
		if (Q[i] <= Q[i - 1])
			break;
	}
	return i == j;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

2. 最小堆（优先队列）的判断

最小堆的性质是，根节点小于左右孩子节点即可
所以可以采用 先序遍历的方式，
不过本题比较的是，根节点和孩子节点的k2的值，先序遍历的话，遍历根节点的时候，找不到孩子节点的k2的值
所以我们换个思路就是，遍历孩子节点的同时，传给孩子节点父节点的k2的值，这样就能进行比较了（孩子节点的k2的值需要大于父亲节点）
注意：根节点进行开始递归的时候，传入的值是 根节点的k2的值-1，这样就可以进行正常递归遍历判断！

bool Find(int k2,int s) {
	if (s == -1)
		return true;
	else if (T[s].k2 <= k2)
		return false;
		bool f1=Find(T[s].k2, T[s].l);
		Q.push_back(T[s].k1);
		bool f2=Find(T[s].k2, T[s].r);
		return (f1 && f2);
}
1
2
3
4
5
6
7
8
9
10