PAT A1159 Structure of a Binary Tree (30point(s))

Scroll Down

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 $10^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

解答

#include<iostream>
#include<unordered_map>
#include<cstring>
#include<vector>

using namespace std;

vector<int> in, post;
unordered_map<int, int> idx;
unordered_map<int, int> sibling, parent, lchild, rchild, levels;
bool isFull = true;

void build(int inl, int inr, int postl, int postr, int level) {
	int mid = idx[post[postr]], leftNum = mid - inl - 1;
	levels[in[mid]] = level;
	int l = -1, r = -1;
	if (inl <= mid - 1) {
		l = post[postl + leftNum];
		lchild[in[mid]] = l;
		parent[l] = in[mid];
		build(inl, mid - 1, postl, postl + leftNum, level + 1);
	}
	if (mid + 1 <= inr) {
		r = post[postr - 1];
		rchild[in[mid]] = r;
		parent[r] = in[mid];
		build(mid + 1, inr, postl + leftNum + 1, postr - 1, level + 1);
	}
	if (inl <= mid - 1 && mid + 1 <= inr) {
		sibling[r] = l;
		sibling[l] = r;
	}
	else if(!(inl > mid - 1 && mid + 1 > inr)){
		isFull = false;
	}
}

int main() {
	int n, m;
	scanf("%d", &n);
	in.resize(n), post.resize(n);
	for (int i = 0; i < n; i++) scanf("%d", &post[i]);
	for (int i = 0; i < n; i++) {
		scanf("%d", &in[i]);
		idx[in[i]] = i;
	}
	build(0, n - 1, 0, n - 1, 1);
	scanf("%d", &m);
	int A, B;
	char str[10], tmp[10], s1[10], s2[10];
	for(int i = 0;i<m;i++){
		scanf("%s %s ", tmp, str);
		// It is a full tree
		if (strcmp(tmp, "It") == 0) {
			printf("%s\n", isFull ? "Yes" : "No");
			scanf("%s %s %s", tmp, s1, s2);// 坑点1
		}
		else {
			A = atoi(tmp);
			if (strcmp(str, "and") == 0) {
				scanf("%d %s %s", &B, s1, str);
				// A and B are siblings
				if (strcmp(str, "siblings") == 0) 
					printf("%s\n", sibling.find(A)!=sibling.end() && sibling[A] == B ? "Yes" : "No");
				// A and B are on the same level
				else {
					printf("%s\n", levels.find(A) != levels.end() && levels.find(B) != levels.end() && 
						levels[A] == levels[B] ? "Yes" : "No");
					scanf("%s %s %s", s1, s2, tmp);
				}
			}
			else {
				// A is the root
				scanf("%s %s", s2, str);
				if (strcmp(str, "root") == 0) printf("%s\n", post[n - 1] == A ? "Yes" : "No");
				else if(strcmp(str, "parent") == 0) {//A is the parent of B
					scanf("%s %d", s1, &B);
					printf("%s\n", parent.find(B) != parent.end() && parent[B] == A ? "Yes" : "No");
				}
				else if (strcmp(str, "left") == 0) {// A is the left child of B
					scanf("%s %s %d", s1, s2, &B);
					printf("%s\n", lchild.find(B) != lchild.end() && lchild[B] == A ? "Yes" : "No");
				}
				else if (strcmp(str, "right") == 0) {// A is the right child of B
					scanf("%s %s %d", s1, s2, &B);
					printf("%s\n", rchild.find(B) != rchild.end() && rchild[B] == A ? "Yes" : "No");
				}
			}
		}
	}
	return 0;
}