PAT甲级【2019年3月考题】——A1159 Structure_of_a

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 10^310
3
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

【声明】

　　由于此题还未上PAT官网题库，故没有测试集，仅仅是通过了样例，若发现错误，感谢留言指正。

Solution：

　　这道题不难，先通过后序和中序重构整颗二叉树，在重构时，使用hash表来存储每个节点值对应的节点，这样就可以解决后面询问是不是父节点和左右子节点的问题。

　　然后使用DFS来遍历整棵树，得到每个节点的深度值，其中记得记录每个节点的姐妹节点是谁，并进行判断是不是完整二叉树。

　　到此，对于题目中的7个问题都有相应的记录进行解决

　　唯一麻烦的是，对于问题的处理，题目是输入一整句话，那么判断属于哪个问题和将其中的关键数字取出来就比较麻烦，我是使用string中的find来判断属于哪个问题，并使用循环来获取数字，当然你也可以使用istringstream函数进行切割获取数据。

 #include <iostream>

 #include <queue>

 #include <vector>

 #include <string>

 #include <unordered_map>

 using namespace std;

 struct Node

 {

     int val;

     Node *l, *r;

     Node(int a = ) :val(a), l(nullptr), r(nullptr) {}

 };

 int n, m;

 bool isfullTree = true;

 vector<int>post, in, siblings(, -), level(, -);

 unordered_map<int, Node*>map;

 Node* creatTree(int inL, int inR, int postL, int postR)//重建二叉树

 {

     if (inL > inR)

         return nullptr;

     Node *root = new Node(post[postR]);

     map[root->val] = root;//记录节点对应的key值

     int k = inL;

     while (k <= inR && in[k] != post[postR])++k;

     int nums = k - inL;

     root->l = creatTree(inL, k - , postL, postL + nums - );

     root->r = creatTree(k + , inR, postL + nums, postR - );

     return root;

 }

 void DFS(Node *root, int L)

 {

     if (root == nullptr)

         return;

     if ((root->l == nullptr && root->r) || (root->r == nullptr && root->l))

         isfullTree = true;//不是完全二叉树

     level[root->val] = L;//记录层数

     if (root->l&& root->r)//记录姐妹节点

     {

         siblings[root->l->val] = root->r->val;

         siblings[root->r->val] = root->l->val;

     }

     DFS(root->l, L + );

     DFS(root->r, L + );

 }

 vector<int> getNumber(const string &str, bool isOneNumber)//获取数据

 {

     vector<int>res;

     int a = ;

     for (int i = ; i < str.length(); ++i)

     {

         if (isdigit(str[i]))

             a = a *  + str[i] - '';

         else if (a > )

         {

             res.push_back(a);

             a = ;

             if (isOneNumber || res.size() == )//就输出一个字符就行

                 break;

         }

     }

     if (!isOneNumber && res.size() < )//获取处于最后的数字

         res.push_back(a);

     return res;

 }

 int main()

 {

     cin >> n;

     post.resize(n);

     in.resize(n);

     for (int i = ; i < n; ++i)

         cin >> post[i];

     for (int i = ; i < n; ++i)

         cin >> in[i];

     Node *root = creatTree(, n - , , n - );

     DFS(root, );//获取层数

     cin >> m;

     getchar();

     while (m--)

     {

         string str;

         getline(cin, str);

         if (str.find("root", ) != -)//查询根节点

         {

             vector<int>res = getNumber(str, true);

             if (root->val == res[])

                 printf("Yes\n");

             else

                 printf("No\n");

         }

         else if (str.find("siblings", ) != -)//查询姐妹节点

         {

             vector<int>res = getNumber(str, false);

             if (siblings[res[]] == res[])

                 printf("Yes\n");

             else

                 printf("No\n");

         }

         else if (str.find("parent", ) != -)//查询父节点

         {

             vector<int>res = getNumber(str, false);

             if ((map[res[]]->l && map[res[]]->l->val == res[]) ||

                 (map[res[]]->r && map[res[]]->r->val == res[]))

                 printf("Yes\n");

             else

                 printf("No\n");

         }

         else if (str.find("left", ) != -)//左节点

         {

             vector<int>res = getNumber(str, false);

             if (map[res[]]->l && map[res[]]->l->val == res[])

                 printf("Yes\n");

             else

                 printf("No\n");

         }

         else if (str.find("right", ) != -)//右节点

         {

             vector<int>res = getNumber(str, false);

             if (map[res[]]->r && map[res[]]->r->val == res[])

                 printf("Yes\n");

             else

                 printf("No\n");

         }

         else if (str.find("level", ) != -)//同样的深度

         {

             vector<int>res = getNumber(str, false);

             if (level[res[]]==level[res[]])

                 printf("Yes\n");

             else

                 printf("No\n");

         }

         else if (str.find("full", ) != -)//是不是完整二叉树

         {

             if (isfullTree)

                 printf("Yes\n");

             else

                 printf("No\n");

         }

     }

     return ;

 }

我的代码有点繁琐，后然我逛博客发现了一个更简便的字符处理函数sscanf，还有就是由于重构二叉树的同时就是一个DFS的过程，这样我们就可以将其深度值得到。当然，我感觉我的代码还是有点优点的，不是么 ^_^.

附带博主代码：

 #include<iostream>

 #include<vector>

 #include<queue>

 #include<algorithm>

 #include<string>

 #include<cstring>

 #include<unordered_map>

 #include<unordered_set>

 using namespace std;

 const int maxn=;

 const int INF=0x3f3f3f3f;

 unordered_map<int,int> level,parents;

 struct node {

     int data;

     int layer;

     node *lchild,*rchild;

 };

 vector<int> post,in;

 node* newNode(int data,int layer) {

     node* root=new node;

     root->data=data;

     root->layer=layer;

     level[data]=layer;

     root->lchild=root->rchild=NULL;

     return root;

 }

 bool flag=true;

 node* create(int parent,int postLeft,int postRight,int inLeft,int inRight,int layer) {

     if(postLeft>postRight) return NULL;

     node* root=newNode(post[postRight],layer);

     parents[root->data]=parent;

     int index=inLeft;

     while(in[index]!=root->data) index++;

     int numLeft=index-inLeft;

     root->lchild=create(root->data,postLeft,postLeft+numLeft-,inLeft,index-,layer+);

     root->rchild=create(root->data,postLeft+numLeft,postRight-,index+,inRight,layer+);

     //如果有叶子，就必须有两片叶子

     if((root->lchild || root->rchild ) && (!root->lchild || !root->rchild)) flag=false;

     return root;

 }

 int main() {

     int n,m;

     unordered_map<int,int> ppos,ipos;

     scanf("%d",&n);

     post.resize(n);

     in.resize(n);

     for(int i=; i<n; i++) {

         scanf("%d",&post[i]);

         ppos[post[i]]=i;

     }

     for(int i=; i<n; i++) {

         scanf("%d",&in[i]);

         ipos[in[i]]=i;

     }

     node* root = create(n-,,n-,,n-,);

     scanf("%d\n",&m);

     string ask;

     for(int i=; i<m; i++) {

         getline(cin,ask);

         int num1=,num2=;

         if(ask.find("root")!=string::npos) {

             sscanf(ask.c_str(),"%d is the root",&num1);

             if(ppos[num1]==n-) puts("Yes");

             else puts("No");

         } else if(ask.find("siblings")!=string::npos) {

             sscanf(ask.c_str(),"%d and %d are siblings",&num1,&num2);

             if(level[num1]==level[num2] && parents[num1]==parents[num2]) puts("Yes");

             else puts("No");

         } else if(ask.find("parent")!=string::npos) {

             sscanf(ask.c_str(),"%d is the parent of %d",&num1,&num2);

             if(parents[num2]==num1) puts("Yes");

             else puts("No");

         } else if(ask.find("left")!=string::npos) {

             sscanf(ask.c_str(),"%d is the left child of %d",&num1,&num2);

             if(parents[num1]==num2 && ipos[num1]<ipos[num2]) puts("Yes");

             else puts("No");

         } else if(ask.find("right")!=string::npos) {

             sscanf(ask.c_str(),"%d is the right child of %d",&num1,&num2);

             if(parents[num1]==num2 && ipos[num1]>ipos[num2]) puts("Yes");

             else puts("No");

         } else if(ask.find("same")!=string::npos) {

             sscanf(ask.c_str(),"%d and %d are on the same level",&num1,&num2);

             if(level[num1]==level[num2]) puts("Yes");

             else puts("No");

         } else if(ask.find("full")!=string::npos) {

             if(flag) puts("Yes");

             else puts("No");

         }

     }

     return ;

 }

巴特西

PAT甲级【2019年3月考题】——A1159 Structure_of_a_BinaryTree【30】

最新文章

热门文章