首页 > 代码库 > pat-笛卡尔树

pat-笛卡尔树

4-09. 笛卡尔树(25)

时间限制
400 ms
内存限制
32000 kB
代码长度限制
8000 B
判题程序
Standard

笛卡尔树是一种特殊的二叉树,其结点包含两个关键字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


----------------------------------------------------------------------------------------------------------
讲一下解体思路:k1的结构是一颗有序二叉树,中序遍历应该是一个从小到达排序的序列。所以我们可以先得到k1中序遍历结果,排序后和原结果对比。如果不变,说明原结果是有序的。则k1的值的确构成有序二叉树。k2的检测可以穿插在遍历的过程中,满足都比左右子节点小的条件即可。最后还有一个小问题,怎么组织树的结构,我用了一个向量存储每个节点,将题中的下表利用起来。在输入的同时可以记录k2的最小值对应的下标,即根节点。

代码:
// pat-4.09.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include"iostream"
#include"algorithm"
#include"vector"

using namespace std;
#define null NULL
bool cmp(int a,int b)
{
	return a<b;
}
class node{
public:
	int k1;
	int k2;
	node* left;
	node* right;
	node():k1(0),k2(0),left(NULL),right(NULL){};
};

vector<node*> tree;
vector<int> ans;
bool flag=true;

void  dfs(node* root)
{   
	if(root==NULL)
		return;
	if((root->left!=NULL&&(root->k2>root->left->k2))||(root->right!=NULL&&(root->k2>root->right->k2)))
	{//min heap
	    flag=false;
		return;
	}
	if((root->left!=NULL&&root->k1<root->left->k1)||(root->right!=NULL&&root->k1>root->right->k1))
	{//binary tree
	    flag=false;
		return;
	}
	dfs(root->left);
	ans.push_back(root->k1);
	dfs(root->right);

}

int main()
{
	int n=0;
	cin>>n;
	for(int i=0;i<n;i++){
	  node* temp = new node();
	  tree.push_back(temp);
	}
	//tree.resize(n);
	int k1=0,k2=0,left=0,right=0;
	int min=999999,root=0;
	for(int i=0;i<n;i++){
	   cin>>k1>>k2>>left>>right;
	  // node* no=new node();
	   node* no=tree[i];
	   no->k1=k1;
	   no->k2=k2;
	   if(left!=-1)
		 no->left=tree[left];
	   if(right!=-1)
		no->right=tree[right];
	   if(k2<min)
	   {
		   min=k2;
		   root=i;
	   }
	   //tree[i]=(no);
	}
	dfs(tree[root]);
	if(!flag){
		cout<<"NO"<<endl;
		return 0;
	}
	if(ans.size()<n){
		cout<<"NO"<<endl;
		return 0;
	}
	vector<int> tempans=ans;
	sort(ans.begin(),ans.end(),cmp);
	for(int i=0;i<n;i++){//compare 
		if(ans[i]!=tempans[i]){
			cout<<"NO"<<endl;
			return 0;
		}
	}
	cout<<"YES"<<endl;
	return 0;
}


pat-笛卡尔树