# PAT 2019甲级春季考试真题4 Structure of a Binary Tree

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.

• 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  (), 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  and are separated by a space.

Then another positive integer  () is given, followed by  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

#include <bits/stdc++.h>
using namespace std;
struct node{
int data;
node *lchild, *rchild, *father;
int level;
node(int n){
data = n;
lchild = rchild = NULL;
level = 0;
}
};
vector<int> post, in;
unordered_map<int, int> pos, level;
unordered_map<int, node*> int_node;

node* Build(int postL, int postR, int inL, int inR){
if(postL > postR) return NULL;
node *root = new node(post[postR]);  //root->data = post[postR]
int lchildlen = pos[root->data] - inL;
root->lchild = Build(postL, postL + lchildlen - 1, inL, pos[root->data] - 1);
root->rchild = Build(postL + lchildlen, postR - 1, pos[root->data] + 1, inR);
return root;
}
bool isFullTree = true;
void dfs(node* root, int depth = 1, node* last = NULL){
if(root == NULL) return;
root->level = depth;
int_node[root->data] = root;
level[root->data] = root->level;
root->father = last;
if((root->lchild && !root->rchild) || (root->rchild && !root->rchild)){
isFullTree = false;
}
dfs(root->lchild, depth + 1, root);
dfs(root->rchild, depth + 1, root);
}

int main(){
int cnt;
cin >> cnt;
post.resize(cnt), in.resize(cnt);
for(int & i : post) cin >> i;  //Read Post Seq
for(int i = 0; i < cnt; i++){  //Read In Seq
cin >> in[i];
pos[in[i]] = i;
}
node *T = Build(0, cnt - 1, 0, cnt - 1);
dfs(T);
int qcnt;
cin >> qcnt;
string hahaha;  //xi shou \n
getline(cin, hahaha);
for(int i = 0; i < qcnt; i++){
string query;
getline(cin, query);
if(query[query.size() - 1] == 't'){  // 15 is the root
string _root;
for(auto c : query){
if(c != ' ') _root += c;
else break;
}
if(T->data == stoi(_root)) cout << "Yes\n";
else cout << "No\n";
}else if(query[query.size() - 1] == 's'){ // 8 and 2 are siblings
//////////////////////////////////
string _l, _r;
int kongge = 0;
for(auto c : query){
if(c == ' ')
kongge++;
else{
if(kongge == 0) _l += c;
if(kongge == 2) _r += c;
if(kongge > 2) break;
}
}
int _a = stoi(_l), _b = stoi(_r);
if(int_node[_a]->father == int_node[_b]->father) cout << "Yes\n";
else cout << "No\n";
//////////////////////////////////
}else if(query[query.size() - 1] == 'l'){ //7 and 11 are on the same level
string _l, _r;
int kongge = 0;
for(auto c : query){
if(c == ' ')
kongge++;
else{
if(kongge == 0) _l += c;
if(kongge == 2) _r += c;
if(kongge > 2) break;
}
}
int _a = stoi(_l), _b = stoi(_r);
if(level[_a] == level[_b]) cout << "Yes\n";
else cout << "No\n";
}else if(query[query.size() - 1] == 'e'){ //It is a full tree
if(isFullTree) cout << "Yes\n";
else cout << "No\n";
}else if(query.find("parent") != string::npos){  //32 is the parent of 11
string _l, _r;
int kongge = 0;
for(auto c : query){
if(c == ' ')
kongge++;
else{
if(kongge == 0) _l += c;
if(kongge == 5) _r += c;
if(kongge > 5) break;
}
}
int _a = stoi(_l), _b = stoi(_r);
if((int_node[_a]->lchild && int_node[_a]->lchild->data == _b) || (int_node[_a]->rchild && int_node[_a]->rchild->data == _b))
cout << "Yes\n";
else cout << "No\n";
}else if(query.find("left") != string::npos){ ////23 is the left child of 16
string _l, _r;
int kongge = 0;
for(auto c : query){
if(c == ' ')
kongge++;
else{
if(kongge == 0) _l += c;
if(kongge == 6) _r += c;
if(kongge > 6) break;
}
}
int _a = stoi(_l), _b = stoi(_r);
if(int_node[_b]->lchild && int_node[_b]->lchild->data == _a)
cout << "Yes\n";
else cout << "No\n";
}else if(query.find("right") != string::npos){  //28 is the right child of 2
string _l, _r;
int kongge = 0;
for(auto c : query){
if(c == ' ')
kongge++;
else{
if(kongge == 0) _l += c;
if(kongge == 6) _r += c;
if(kongge > 6) break;
}
}
int _a = stoi(_l), _b = stoi(_r);
if(int_node[_b]->rchild && int_node[_b]->rchild->data == _a)
cout << "Yes\n";
else cout << "No\n";
}
}
return 0;
}