1159 Structure of a Binary Tree – PAT甲级真题

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 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

题目大意：假设二叉树中的所有值都是不同的正整数，给定后序和中序遍历可以唯一确定一棵二叉树。给出一系列关于二叉树结构的语句，判断它们是否正确，语句是以下之一：A是根结点，A和B是兄弟姐妹，A是B的父结点，A是B的左孩子，A是B的右孩子，A和B在同一层，这是一棵full tree。（两个结点在同一层，意味着这两个结点具有同样深度；full binary tree是指除了叶子结点外，每个结点都有两个孩子）。输入样例：第一行给出正整数N，即二叉树中结点的总数；第二行给出后序遍历序列，第三行给出中序遍历序列。一行中所有数字不超过10的3次方，并且用空格分隔。然后给出一个正整数M，然后是M行语句，保证语句的A和B都在树中。输出样例：对于每条语句，如果正确，则输出Yes，否则输出No。
分析：中序存储在In数组中，后序存储在Post数组中，根据中序和后序建树，Tree中存储树上结点的相关信息，下标即表示结点的值，其中lchild存储左孩子下标，rchild存储右孩子下标，parent存储父结点下标，将这些初始化为-1表示不存在，level存储深度，此外，root为根节点的值，Full标记是否是full tree，f判断当前语句是否正确，最后根据f的值输出Yes或No~

#include<iostream>
using namespace std;
struct node {
    int lchild, rchild, parent, level;
    node() {
        lchild = rchild = parent = -1;
    }
}Tree[1002];
int n, m, a, b, root, f, Full;
int In[32], Post[32];
string t;
int deal(int R, int start, int end, int Pa) {
    if(start > end) return -1;
    int i = start;
    while(i < end && In[i] != Post[R]) i++;
    Tree[Post[R]].parent = Pa;
    Tree[Post[R]].level = Tree[Pa].level + 1;
    Tree[Post[R]].lchild = deal(R - 1 - end + i, start, i - 1, Post[R]);
    Tree[Post[R]].rchild = deal(R - 1, i + 1, end, Post[R]);
    if (Tree[Post[R]].lchild * Tree[Post[R]].rchild < 0) Full = 1;
    return Post[R];
}
int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> Post[i];
    } 
    for (int i = 0; i < n; i++) 
        cin >> In[i];
    root = Post[n - 1];
    deal(n - 1, 0, n - 1, 1001);
    cin >> m;
    while (m--) {
        f = 0;
        cin >> t;
        if (t == "It") {
            cin >> t >> t >> t >> t;
            if (Full) cout << "No\n";
            else cout << "Yes\n";
            continue;
        } 
        a = stoi(t);
        cin >> t;
        if (t == "is") {
            cin >> t >> t;
            if (t == "root") {
                if (a == root) f = 1;
            } else if (t == "parent") {
                cin >> t >> b;
                if (Tree[b].parent == a) f = 1;
            } else if (t == "left") {
                cin >> t >> t >> b;
                if (Tree[b].lchild == a) f = 1;
            } else {
                cin >> t >> t >> b;
                if (Tree[b].rchild == a) f = 1;
            }
        } else {
            cin >> b >> t >> t;
            if (t == "siblings") {
                if (Tree[a].parent == Tree[b].parent) f = 1;
            } else {
                cin >> t >> t >> t;
                if (Tree[a].level == Tree[b].level) f = 1;
            }
        }
        cout << (f ? "Yes\n" : "No\n");
    }
    return 0;
}

#include<iostream>

using namespace std;

struct node {

int lchild, rchild, parent, level;

node() {

lchild = rchild = parent = -1;

}

}Tree[1002];

int n, m, a, b, root, f, Full;

int In[32], Post[32];

string t;

int deal(int R, int start, int end, int Pa) {

if(start > end) return -1;

int i = start;

while(i < end && In[i] != Post[R]) i++;

Tree[Post[R]].parent = Pa;

Tree[Post[R]].level = Tree[Pa].level + 1;

Tree[Post[R]].lchild = deal(R - 1 - end + i, start, i - 1, Post[R]);

Tree[Post[R]].rchild = deal(R - 1, i + 1, end, Post[R]);

if (Tree[Post[R]].lchild * Tree[Post[R]].rchild < 0) Full = 1;

return Post[R];

}

int main() {

cin >> n;

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

cin >> Post[i];

}

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

cin >> In[i];

root = Post[n - 1];

deal(n - 1, 0, n - 1, 1001);

cin >> m;

while (m--) {

f = 0;

cin >> t;

if (t == "It") {

cin >> t >> t >> t >> t;

if (Full) cout << "No\n";

else cout << "Yes\n";

continue;

}

a = stoi(t);

cin >> t;

if (t == "is") {

cin >> t >> t;

if (t == "root") {

if (a == root) f = 1;

} else if (t == "parent") {

cin >> t >> b;

if (Tree[b].parent == a) f = 1;

} else if (t == "left") {

cin >> t >> t >> b;

if (Tree[b].lchild == a) f = 1;

} else {

cin >> t >> t >> b;

if (Tree[b].rchild == a) f = 1;

}

} else {

cin >> b >> t >> t;

if (t == "siblings") {

if (Tree[a].parent == Tree[b].parent) f = 1;

} else {

cin >> t >> t >> t;

if (Tree[a].level == Tree[b].level) f = 1;

}

cout << (f ? "Yes\n" : "No\n");

}

return 0;

}

❤ 点击这里 -> 订阅《PAT | 蓝桥 | LeetCode学习路径 & 刷题经验》by 柳婼

❤ 点击这里 -> 订阅《从放弃C语言到使用C++刷算法的简明教程》by 柳婼

❤ 点击这里 -> 订阅PAT甲级乙级、蓝桥杯、GPLT天梯赛、LeetCode题解离线版