Home PAT 1159 Structure of a Binary Tree
Post
Cancel

PAT 1159 Structure of a Binary Tree

Link

Given the postorder and inorder traversal sequences, a binary tree can be uniquely determined.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
#include <cctype>
#include <queue>
using namespace std;
int n,m,post[35],in[35],level[1010];
string s;
bool isFull=true;
struct node{
    int parent,left=-1,right=-1;
}tree[1010];
int Build(int inLeft,int inRight,int postLeft,int postRight){
    // cout<<inLeft<<" "<<inRight<<" "<<postLeft<<" "<<postRight<<endl;
    if(inLeft>inRight) return -1;
    if(inLeft==inRight) return in[inLeft];
    int root=post[postRight],index=0;
    for(int i=inLeft;i<=inRight;++i)
        if(in[i]==root){
            index=i;
            break;
        }
    tree[root].left=Build(inLeft,index-1,postLeft,postLeft+(index-1-inLeft));
    if(tree[root].left!=-1) tree[tree[root].left].parent=root;
    tree[root].right=Build(index+1,inRight,postRight-1-(inRight-index-1),postRight-1);
    if(tree[root].right!=-1) tree[tree[root].right].parent=root;
    if((tree[root].left==-1&&tree[root].right!=-1)||(tree[root].left!=-1&&tree[root].right==-1)) isFull=false;
    return root;
}
void BFS(int x){
    level[x]=1;
    queue<int>q;
    q.push(x);
    while(!q.empty()){
        x=q.front();
        q.pop();
        if(tree[x].left!=-1){
            level[tree[x].left]=level[x]+1;
            q.push(tree[x].left);
        }
        if(tree[x].right!=-1){
            level[tree[x].right]=level[x]+1;
            q.push(tree[x].right);
        }
    }
}
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]);
    int root=Build(1,n,1,n);
    BFS(root);
    scanf("%d",&m);
    getchar();
    while(m--){
        getline(cin,s);
        if(!isdigit(s[0])){
            printf("%s\n",isFull?"Yes":"No");
        }else{
            int pos=s.find(" ");
            int a=stoi(s.substr(0,pos));
            if(s[pos+1]=='a'){
                s=s.substr(pos+1);
                pos=s.find(" ");
                s=s.substr(pos+1);
                pos=s.find(" ");
                int b=stoi(s.substr(0,pos));
                if(s[s.size()-1]=='s'){
                    printf("%s\n",tree[a].parent==tree[b].parent?"Yes":"No");
                }else{
                    printf("%s\n",level[a]==level[b]?"Yes":"No");
                }
            }else{
                if(s[s.size()-1]=='t'){
                    printf("%s\n",a==root?"Yes":"No");
                }else{
                    pos=s.find("of");
                    int b=stoi(s.substr(pos+3));
                    pos=s.find("the");
                    if(s[pos+4]=='p'){
                        printf("%s\n",tree[b].parent==a?"Yes":"No");
                    }else if(s[pos+4]=='l'){
                        printf("%s\n",tree[b].left==a?"Yes":"No");
                    }else{
                        printf("%s\n",tree[b].right==a?"Yes":"No");
                    }
                }
            }
        }
    }
    return 0;
}
This post is licensed under CC BY 4.0 by the author.