7-31 笛卡尔树 (25 分)
笛卡尔树是一种特殊的二叉树，其结点包含两个关键字K1和K2。首先笛卡尔树是关于K1的二叉搜索树，即结点左子树的所有K1值都比该结点的K1值小，右子树则大。其次所有结点的K2关键字满足优先队列（不妨设为最小堆）的顺序要求，即该结点的K2值比其子树中所有结点的K2值小。给定一棵二叉树，请判断该树是否笛卡尔树。
输入格式:
输入首先给出正整数N（≤1000），为树中结点的个数。随后N行，每行给出一个结点的信息，包括：结点的K1值、K2值、左孩子结点编号、右孩子结点编号。设结点从0~(N-1)顺序编号。若某结点不存在孩子结点，则该位置给出−1。
输出格式:
输出YES如果该树是一棵笛卡尔树；否则输出NO。
输入样例1:
1
2
3
4
5
6
7
| 6
8 27 5 1
9 40 -1 -1
10 20 0 3
12 21 -1 4
15 22 -1 -1
5 35 -1 -1
|
输出样例1:
输入样例2:
1
2
3
4
5
6
7
| 6
8 27 5 1
9 40 -1 -1
10 20 0 3
12 11 -1 4
15 22 -1 -1
50 35 -1 -1
|
输出样例2:
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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
| #include<iostream>
#include<vector>
using namespace std;
struct node{
int K1, K2, lchild, rchild;
};
int N;
node Node[1000];
vector<int> inOrder;
void inOrderTraversal(int head);
bool judge1(int head);
bool judge2(int head);
int main(){
std::ios::sync_with_stdio(false);
cin >> N;
bool flag[N];
fill(flag, flag + N, false);
for(int i = 0; i < N; i++){
cin >> Node[i].K1 >> Node[i].K2 >> Node[i].lchild >> Node[i].rchild;
if(Node[i].lchild != -1){
flag[Node[i].lchild] = true;
}
if(Node[i].rchild != -1){
flag[Node[i].rchild] = true;
}
}
int head = -1;
for(int i = 0; i < N; i++){
if(!flag[i]){
head = i;
break;
}
}
if(judge1(head) && judge2(head)){
cout << "YES" << endl;
}else{
cout << "NO" << endl;
}
return 0;
}
void inOrderTraversal(int head){
if(head == -1){
return;
}
inOrderTraversal(Node[head].lchild);
inOrder.push_back(Node[head].K1);
inOrderTraversal(Node[head].rchild);
}
bool judge1(int head){
inOrderTraversal(head);
for(int i = 1; i < inOrder.size(); i++){
if(inOrder[i] <= inOrder[i - 1]){
return false;
}
}
return true;
}
bool judge2(int head){
if(head == -1){
return true;
}
if(Node[head].lchild != -1 && Node[Node[head].lchild].K2 <= Node[head].K2){
return false;
}
if(Node[head].rchild != -1 && Node[Node[head].rchild].K2 <= Node[head].K2){
return false;
}
return judge2(Node[head].lchild) && judge2(Node[head].rchild);
}
|
