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.
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$ ( $\leq 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 $1 0^{3}$ and are separated by a space.

Then another positive integer $M$ ( $\leq 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

给定一棵二叉树的后序、中序序列，接着给定几个命题，判断是否正确。

这道题我写麻烦了，使用sscanf会比较简单。

以后有时间了再优化

#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;
}

斐斐のBlog