您的位置: 首页  >  文章  >  PAT-2019年春季考试-甲级-Structure of a Binary Tree

PAT-2019年春季考试-甲级-Structure of a Binary Tree

分类: 文章 • 2024-09-01 17:39:04

7-4 Structure of a Binary Tree （30 分)
作者: 陈越
单位: 浙江大学
时间限制: 400 ms
内存限制: 64 MB
代码长度限制: 16 KB
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 1000 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

题意：这两天再写天梯赛的题目，发现和L3有一道几乎一模一样。。
二叉搜索树基本题，比赛的时候过的比第三题多。似乎大家更加喜欢模板题，编码能力有待提高吧（个人觉得第三题考些编码能力）。这道题就是给你一些句子问你对错。

思路：1.必须学会的建树操作。
2.室友当时看题懵了，不知道怎么读入，我这里就是一个单词一个单词读入，然后判断。

小建议：1.建议比赛的时候把样例的树模拟出来，方便调试。
2.对于环境不熟悉，没有开启c++11 导致手写StoI函数。
PAT-2019年春季考试-甲级-Structure of a Binary Tree
也是写了整整一个小时。
好像建树的时候可以再优化下，我在建完树之后又操作了下（可以被优化）。
得到27的时候是因为不知道siblings啥意思，然后就开始枚举。因为感觉也没有什么可以考的，就猜对了，运气还不错，刚刚好ak离场。

总结：PAT考试也告一段落，保持好的状态准备天梯赛，浙大赛，省赛。
如果大家有什么问题欢迎留言~

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+7;
struct node{
    int l,r;
}p[N],pp[N];
int post[N],in[N];
//in post
int build(int l1,int r1,int l2,int r2)
{
    if(r1<l1) return 0;
    int p1,p2;
    p1=l1;
    while(in[p1]!=post[r2]) p1++;
    //printf("!%d\n",in[p1]);
    p2=p1-l1;
    p[p1].l=build(l1,p1-1,l2,l2+p2-1);
    p[p1].r=build(p1+1,r1,l2+p2,r2-1);
    return in[p1];
}
int n;
bool check1()
{
    for(int i=1;i<=n;i++){
        if(p[i].l && p[i].r==0) return false;
        if(p[i].r && p[i].l==0) return false;
    }
    return true;
}
int StoI(string s)
{
    int l=s.length();
    int ans=0;
    for(int i=0;i<l;i++){
        ans=ans*10+s[i]-'0';
    }
    return ans;
}
int dep[N];
void dfs(int x)
{
    if(pp[x].l==0 && pp[x].r==0) return;

    int l=pp[x].l;
    int r=pp[x].r;
    if(l) dep[l]=dep[x]+1,dfs(l);
    if(r) dep[r]=dep[x]+1,dfs(r);
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&post[i]);
    }
    for(int i=1;i<=n;i++){
        scanf("%d",&in[i]);
    }
    build(1,n,1,n);

    for(int i=1;i<=n;i++){
        int now=in[i];
        pp[now].l=p[i].l;
        pp[now].r=p[i].r;

    }
    int now=post[n];
    dfs(now);
    //printf("! %d %d\n",p[23].l,p[23].r);
    int m; scanf("%d",&m);
    for(int i=1;i<=m;i++){
        string s; cin>>s;
        if(s[0]=='I'){
            if(check1()) puts("Yes");
            else puts("No");
            cin>>s;cin>>s;
            cin>>s;cin>>s;
        }else{
            int id1=StoI(s);
            //printf("id1=%d\n",id1);
            cin>>s;
            if(s[0]=='a'){
                cin>>s;
                int id2=StoI(s);
                cin>>s;cin>>s;
                if(s[0]=='o'){
                    //same level
                    if(dep[id1]==dep[id2]) puts("Yes");
                    else puts("No");
                    cin>>s;cin>>s;cin>>s;
                }else{
                    //siblings
                    int flag=0;
                    for(int i=1;i<=n;i++){
                        if(p[i].l==id1 && p[i].r==id2 || p[i].r==id1 && p[i].l==id2) flag=1;
                    }
                    if(flag) puts("Yes");
                    else puts("No");
                }
            }else{
                cin>>s;cin>>s;
                if(s[0]=='r' && s[1]=='o'){
                    //root
                    if(post[n]==id1) puts("Yes");
                    else puts("No");
                }else if(s[0]=='p'){
                    cin>>s;cin>>s;
                    int id2=StoI(s);
                    if(pp[id1].l==id2 || pp[id1].r==id2) puts("Yes");
                    else puts("No");
                }else if(s[0]=='l'){
                     cin>>s;cin>>s;cin>>s;
                     int id2=StoI(s);
                    if(pp[id2].l==id1) puts("Yes");
                    else puts("No");
                }else if(s[0]=='r'){
                     cin>>s;cin>>s;cin>>s;
                     int id2=StoI(s);
                    if(pp[id2].r==id1) puts("Yes");
                    else puts("No");
                }
            }
        }
    }
}
/*
9
16 7 11 32 28 2 23 8 15
16 23 7 32 11 2 28 15 8
*/

相关推荐