2019.3 PAT甲级-4 Structure of a Binary Tree (30 分) 二叉树的判断（后序中序建树）

浅浅的花香味﹌ 2024-04-18 09:25 49阅读 0赞

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 103 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

**题意：**根据给定的后序和前序遍历建树，之后有m个询问，分别是题目里的七个问题，输出Yes/No。

**思路：**用后序和前序遍历建树，用l,r数组存放每个结点的左右子树，然后用getline读入问题，用substr截取关键字判断问题类型，然后用字符串流截取数字，然后做相应的判断。其中判断层数是否相同时，用深搜了一遍把每个节点的深度存在le数组中了。

#include<stdio.h>
    #include<string.h>
    #include<math.h>
    #include<iostream>
    #include<string>
    #include<sstream>
    #include<algorithm>
    #include<map>
    #include<set>
    #include<queue>
    #include<stack>
    #include<vector>
    using namespace std;
    #define inf 0x3f3f3f3f
    #define LL long long
    int post[1055],in[1055],le[1055];
    int l[1005],r[1005],n;
    int dfs(int postl,int postr,int inl,int inr)
    {
    	if(postl>postr)return -1;
    	int root=post[postr];
    	int pos=inl;
    	while(in[pos]!=root)pos++;
    	int cnt=pos-inl;
    	l[root]=dfs(postl,postl+cnt-1,inl,pos-1);
    	r[root]=dfs(postl+cnt,postr-1,pos+1,inr);
    	return root;
    }
    void level(int x,int h)
    {
    	le[x]=h;
    	if(l[x]!=-1) level(l[x],h+1);
    	if(r[x]!=-1) level(r[x],h+1);	
    }
    int main()
    {
    	int m,i,j;
    	memset(l,-1,sizeof l);
    	memset(r,-1,sizeof r);
    	scanf("%d",&n);
    	for(i=1;i<=n;i++)
    	scanf("%d",&post[i]);
    	for(i=1;i<=n;i++)
    	scanf("%d",&in[i]);
    	dfs(1,n,1,n);
    	int root=post[n];
    	scanf("%d",&m);
    	getchar();
    	while(m--)
    	{
    		string s,op,a[1005];
    		int p=0,f=1,x,y;
    		getline(cin,s);
    		stringstream ss(s);		
    		while(ss>>op)
    		a[p++]=op;
    		if(s.find("root")!=-1)
    		{
    			stringstream su(a[0]);
    			su>>x;
    			if(x==root) f=0;
    		}
    		else if(s.find("siblings")!=-1)
    		{
    			stringstream su(a[0]);
    			su>>x;
    			stringstream sp(a[2]);
    			sp>>y;
    			int xf=0;
    			for(i=1;i<=n;i++)
    			{
    				if(l[post[i]]==x&&r[post[i]]==y)
    				{
    					xf=1;
    					break;
    				}
    				if(l[post[i]]==y&&r[post[i]]==x)
    				{
    					xf=1;
    					break;
    				}
    			}
    			if(xf)f=0;
    		}
    		else if(s.find("parent")!=-1)
    		{
    			stringstream su(a[0]);
    			su>>x;
    			stringstream sp(a[5]);
    			sp>>y;
    			//cout<<x<<" !!" <<y<<endl;
    			if(l[x]==y||r[x]==y)
    			f=0;
    		}
    		else if(s.find("left")!=-1)
    		{
    			stringstream su(a[0]);
    			su>>x;
    			stringstream sp(a[6]);
    			sp>>y;
    			if(l[y]==x)f=0;
    		}
    		else if(s.find("right")!=-1)
    		{
    			stringstream su(a[0]);
    			su>>x;
    			stringstream sp(a[6]);
    			sp>>y;
    			if(r[y]==x)f=0;
    		}
    		else if(s.find("level")!=-1)
    		{
    			level(root,0);
    			stringstream su(a[0]);
    			su>>x;
    			stringstream sp(a[2]);
    			sp>>y;
    			if(le[x]==le[y]) f=0;
    		}
    		else if(s.find("tree")!=-1)
    		{
    			int xf=0;
    			for(i=1;i<=n;i++)
    			{
    				if(l[post[i]]==-1&&r[post[i]]==-1)continue;
    				if(l[post[i]]!=-1&&r[post[i]]!=-1)continue;
    				xf=1;
    			}
    			if(xf==0)f=0;
    		}
    		if(f==0)printf("Yes\n");
    		else printf("No\n");
    	}
    }