PAT 2019-3 7-4 Structure of a Binary Tree

Description:

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

Then another positive integer M (≤) 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

Keys:

二叉树的存储和遍历

Attention:

sscanf(s.c_str(), "%d %*s %d", &a, &b);
s.find("s") != string::npos;
map<int,node*> mp;

Code:

 /*

 二叉树中各结点值为互不相同的正整数

 给出后序遍历和中序遍历

 判断所给语句是否正确

 根节点

 兄弟

 父结点

 左孩子

 右孩子

 同一层

 满二叉树

 基本思路：

 建树，存储<键值,结点>的映射，存储结点所在层次，判断是否为满二叉树

 sscanf读取字符串

 */

 #include<cstdio>

 #include<string>

 #include<unordered_map>

 #include<iostream>

 using namespace std;

 const int M=1e3+;

 struct node

 {

     int data,high;

     node *lchild,*rchild;

 };

 int in[M],pt[M],hs[M]={},fa[M]={},isfull=;

 unordered_map<int,node*> mp;

 node *Create(int ptL, int ptR, int inL, int inR, int layer, int father)

 {

     if(ptL > ptR)

         return NULL;

     node *root = new node;

     root->data = pt[ptR];

     root->high = layer;

     int k;

     for(k=inL; k<=inR; k++)

         if(in[k]==pt[ptR])

             break;

     int numLeft = k-inL;

     root->lchild = Create(ptL,ptL+numLeft-,inL,k-,layer+, root->data);

     root->rchild = Create(ptL+numLeft,ptR-,k+,inR,layer+, root->data);

     hs[root->data]=;

     fa[root->data]=father;

     mp[root->data] = root;

     if((root->lchild==NULL&&root->rchild!=NULL) || (root->lchild!=NULL&&root->rchild==NULL))

         isfull=;

     return root;

 }

 int main()

 {

 #ifdef ONLINE_JUDGE

 #else

     freopen("Test.txt", "r", stdin);

 #endif // ONLINE_JUDEG

     int n,m;

     scanf("%d", &n);

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

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

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

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

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

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

     while(m--)

     {

         int v1,v2;

         string st;

         getline(cin,st);

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

         {

             sscanf(st.c_str(), "%d is the root", &v1);

             if(v1 == pt[n-])

                 printf("Yes\n");

             else

                 printf("No\n");

         }

         else if(st.find("siblings") != string::npos)

         {

             sscanf(st.c_str(), "%d and %d are siblings", &v1,&v2);

             if(hs[v1]== && hs[v2]== && fa[v1]==fa[v2])

                 printf("Yes\n");

             else

                 printf("No\n");

         }

         else if(st.find("parent") != string::npos)

         {

             sscanf(st.c_str(), "%d is the parent of %d", &v1,&v2);

             if(hs[v1]== && hs[v2]== && fa[v2]==v1)

                 printf("Yes\n");

             else

                 printf("No\n");

         }

         else if(st.find("left") != string::npos)

         {

             sscanf(st.c_str(), "%d is the left child of %d", &v1,&v2);

             if(hs[v1]== && hs[v2]== && mp[v2]->lchild==mp[v1])

                 printf("Yes\n");

             else

                 printf("No\n");

         }

         else if(st.find("right") != string::npos)

         {

             sscanf(st.c_str(), "%d is the right child of %d", &v1,&v2);

             if(hs[v1]== && hs[v2]== && mp[v2]->rchild==mp[v1])

                 printf("Yes\n");

             else

                 printf("No\n");

         }

         else if(st.find("same") != string::npos)

         {

             sscanf(st.c_str(), "%d and %d are on the same level", &v1,&v2);

             if(hs[v1]== && hs[v2]== && mp[v1]->high==mp[v2]->high)

                 printf("Yes\n");

             else

                 printf("No\n");

         }

         else if(st.find("full") != string::npos)

         {

             if(isfull)

                 printf("Yes\n");

             else

                 printf("No\n");

         }

     }

     return ;

 }

巴特西

PAT 2019-3 7-4 Structure of a Binary Tree

Description:

Input Specification:

Output Specification:

Sample Input:

Sample Output:

Keys:

Attention:

Code:

最新文章

热门文章