首页 > 代码库 > 4-09. 笛卡尔树（25）(ZJU_PAT)

4-09. 笛卡尔树（25）(ZJU_PAT)

2024-08-03 21:01:22   223人阅读

题目链接：http://www.patest.cn/contests/ds/4-09


笛卡尔树是一种特殊的二叉树，其结点包含两个关键字K1和K2。首先笛卡尔树是关于K1的二叉搜索树，即结点左子树的所有K1值都比该结点的K1值小，右子树则大。其次所有结点的K2关键字满足优先队列（不妨设为最小堆）的顺序要求，即该结点的K2值比其子树中所有结点的K2值小。给定一棵二叉树，请判断该树是否笛卡尔树。

输入格式说明：

输入首先给出正整数N（<=1000），为树中结点的个数。随后N行，每行给出一个结点的信息，包括：结点的K1值、K2值、左孩子结点编号、右孩子结点编号。设结点从0~(N-1)顺序编号。若某结点不存在孩子结点，则该位置给出-1。

输出格式说明：

输出YES如果该树是一棵笛卡尔树；否则输出NO。

样例输入与输出：

序号输入输出
1
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

YES
2
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

NO
3
7
8 27 5 1
9 40 -1 -1
10 20 0 3
12 22 -1 4
15 21 6 -1
5 35 -1 -1
13 23 -1 -1

NO
4
6
8 27 5 1
9 40 -1 -1
10 20 0 3
12 21 -1 4
11 22 -1 -1
5 35 -1 -1

NO
5
9
11 5 3 -1
15 3 4 7
5 2 6 0
6 8 -1 -1
9 6 -1 8
10 1 2 1
2 4 -1 -1
20 7 -1 -1
12 9 -1 -1

NO
6
1
1 1 -1 -1

YES
PS:

笛卡尔树的中序遍历应为一升序的序列！

代码如下：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn = 1017;
int tag[maxn];
typedef struct
{
	int k1;
	int k2;
	int L;
	int R;
}Node;
vector<int>a;
vector<Node>b;

void Mid_order(Node T)//中序遍历
{
	if(T.L != -1)
	{
		Mid_order(b[T.L]);
	}
	a.push_back(T.k1);
	if(T.R != -1)
	{
		Mid_order(b[T.R]);
	}
}

int is_dkr(Node T)
{
	if(T.L==-1 && T.R==-1)
		return 1;
	else if(T.L!=-1 && T.R==-1)
	{
		if(b[T.L].k2 > T.k2)
			return is_dkr(b[T.L]);
		else
			return 0;
		
	}
	else if(T.L==-1 && T.R!=-1)
	{
		if(b[T.R].k2 > T.k2)
			return is_dkr(b[T.R]);
		else
			return 0;
	}
	else if(T.L!=-1 && T.R!=-1)
	{
		if(b[T.L].k2 > T.k2 && b[T.R].k2 > T.k2)
			return is_dkr(b[T.L]) && is_dkr(b[T.R]);
		else
			return 0;
	}
}

int main()
{
	int n;
	while(~scanf("%d",&n))
	{
		int i, j;
		memset(tag,0,sizeof(tag));
		a.clear();
		b.clear();
		Node c;
		for(i = 0; i < n; i++)
		{
			scanf("%d%d%d%d",&c.k1,&c.k2,&c.L,&c.R);
			if(c.L >= 0)
			{
				tag[c.L] = 1;
			}
			if(c.R >= 0)
			{
				tag[c.R] = 1;
			}
			b.push_back(c);
		}
		int root_node = 0;
		for(i = 0; i < b.size(); i++)
		{
			if(!tag[i])
			{
				root_node = i;//根节点
				break;
			}
		}
		Mid_order(b[root_node]);
		int flag = 0;
		for(i = 1; i < a.size(); i++)
		{
			if(a[i] <= a[i-1])
			{
				flag = 1;
				break;
			}
		}
		if(flag)
		{
			printf("NO\n");
			continue;
		}
		if(!is_dkr(b[root_node]))
		{
			printf("NO\n");
		}
		else
		{
			printf("YES\n");
		}
	}
	return 0;
}


4-09. 笛卡尔树（25）(ZJU_PAT)


联系
我们