A1159 Structure_of_a_BinaryTree (30 points)

后序+中序=树

1. 原文

Suppose that all the keys in a binary tree are distinct positive integers. Given the postorder and inorder traversal sequences, a binary tree can be uniquely determined.

Now given a sequence of statements about the structure of the resulting tree, you are supposed to tell if they are correct or not. A statment is one of the following:

A is the root

A and B are siblings

A is the parent of B

A is the left child of B

A is the right child of B

A and B are on the same level

It is a full tree

Note:

Two nodes are on the same level, means that they have the same depth.

A full binary tree is a tree in which every node other than the leaves has two children.

Input Specification

Each input file contains one test case. For each case, the first line gives a positive integer N (≤30), the total number of nodes in the binary tree. The second line gives the postorder sequence and the third line gives the inorder sequence. All the numbers in a line are no more than $10^3$ and are separated by a space.

Then another positive integer M (≤30) is given, followed by M lines of statements. It is guaranteed that both A and B in the statements are in the tree.

Output Specification

For each statement, print in a line Yes if it is correct, or No if not.

Sample Input

9
16 7 11 32 28 2 23 8 15
16 23 7 32 11 2 28 15 8
7
15 is the root
8 and 2 are siblings
32 is the parent of 11
23 is the left child of 16
28 is the right child of 2
7 and 11 are on the same level
It is a full tree

Sample Output

Yes
No
Yes
No
Yes
Yes
Yes

2. 解析思路

根据后序+中序建立树，记录结点之间的位置关系

node* tree[1010] 值对应结点

int siblings[1010] 分别保存左结点，右结点数值

int level[1010] 保存结点所在层数

输入技巧：sscanf(str.c_str(),”%d is the root”,&num); 直接取出对应数值

3. AC代码

#include<iostream>
#include<string>
using namespace std;
int post[30]={};
int in[30]={};
int level[1010]={};
struct node{
	int data;
	node *lchild,*rchild;
};
node* tree[1010];
int siblings[1010];
node* init(int x){
	node *root = new node;
	root->data = x;
	root->lchild = root->rchild = NULL;
	return root;
}
bool fullTree = true;
void create(int postl,int postr,int inl,int inr,int deep,node* &root){
	if (postl>postr)
	{
		return;
	}
	root = init(post[postr]);
	int i = inl;
	for (; i <= inr; ++i)
	{
		if (in[i]==post[postr])
		{
			break;
		}
	}
	int left = i-inl;
	tree[root->data] = root;
	level[root->data] = deep;
	if (root->lchild!=NULL&&root->rchild!=NULL)
	{
		siblings[root->lchild->data]=root->rchild->data;
		siblings[root->rchild->data]=root->lchild->data;
	}
	if ((root->lchild!=NULL||root->rchild!=NULL)
		&&(root->lchild==NULL||root->rchild==NULL))
	{
		fullTree = false;
	}
	create(postl,postl+left-1,inl,i-1,deep+1,root->lchild);
	create(postl+left,postr-1,i+1,inr,deep+1,root->rchild);

}
int main(){
	int n;
	cin>>n;
	for (int i = 0; i < n; ++i)
	{
		cin>>post[i];
	}
	for (int i = 0; i < n; ++i)
	{
		cin>>in[i];
	}
	node* root = NULL;
	create(0,n-1,0,n-1,0,root);
	int m;
	scanf("%d",&m);
	while(m--){
		string str;
		getline(cin,str);
		if (str.find("root")!=string::npos)
		{
			int num = 0;
			sscanf(str.c_str(),"%d is the root",&num);
			if (num==post[n-1])
			{
				cout<<"Yes"<<endl;
			}else{
				cout<<"No"<<endl;
			}
		}else if (str.find("siblings")!=string::npos)
		{
			int a,b;
			sscanf(str.c_str(),"%d and %d are siblings",&a,&b);
			if (siblings[a]==b&&siblings[b]==a)
			{
				cout<<"Yes"<<endl;
			}else{
				cout<<"No"<<endl;
			}
		}else if(str.find("parent")!=string::npos){
			int a,b;
			sscanf(str.c_str(),"%d is the parent of %d",&a,&b);
			if (tree[a]->lchild->data==b||tree[a]->rchild->data==b)
			{
				cout<<"Yes"<<endl;
			}else{
				cout<<"No"<<endl;
			}
		}else if(str.find("left")!=string::npos){
			int a,b;
			sscanf(str.c_str(),"%d is the left child of %d",&a,&b);
			node *temp = tree[b];
			if (temp->lchild!=NULL&&temp->lchild->data==a)
			{
				cout<<"Yes"<<endl;
			}else{
				cout<<"No"<<endl;
			}
		}else if (str.find("right")!=string::npos){
			int a,b;
			sscanf(str.c_str(),"%d is the right child of %d",&a,&b);
			if (tree[b]->rchild!=NULL&&tree[b]->rchild->data==a)
			{
				cout<<"Yes"<<endl;
			}else{
				cout<<"No"<<endl;
			}
		}else if(str.find("level")!=string::npos){
			int a,b;
			sscanf(str.c_str(),"%d and %d are on the same level",&a,&b);
			if (level[a]==level[b])
			{
				cout<<"Yes"<<endl;
			}else{
				cout<<"No"<<endl;
			}
		}else if(str.find("tree")!=string::npos){
			if (fullTree)
			{
				cout<<"Yes"<<endl;
			}else{
				cout<<"No"<<endl;
			}

		}
	}
	
	return 0;
}