A1159 Structure of a Binary Tree (30 分)

A1159 Structure of a Binary Tree (30 分)

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）是：除了叶子结点以外的其他结点都有两个孩子

思路

1. 简单粗暴快速的方法是：直接根据前序和中序遍历还原二叉树

   • 还原二叉树的过程把结点存储在hash table中（之后判断句子正误的时候就不需要在二叉树中重新去搜索一遍）

     • 建树的结点要加一个树的深度值deep（判断两个结点是否在同一层）
     • 建树过程中把每个结点的父节点也存入hash table （判断一个结点是否为另一个结点的父结点，是否为兄弟结点）

2. 判断语句正误

   • 获取输入语句用：getline(cin, str)
   • 定位语句直接用：string 的 find函数 str.find("root") != string::npos
   • 提取语句中结点的信息：sscanf()函数

3. 这道题主要难点是：

   • 题目意思是否理解
   • 提示中的满二叉树（full binary tree）的定义要注意 (这应该是国外对于full binary tree的定义，与国内常用教材上的定义不同)

AC代码

#include <bits/stdc++.h>
using namespace std;

struct node {
    int data, deep;
    node* left;
    node* right;
};
int N;
bool isfull = true;

vector<int> postorder, inorder;
unordered_map<int, node*> treeNode, parent, leftNode, rightNode;
node* create(int inL, int inR, int postL, int postR, int deep, node* p) {
    if (postL > postR) return nullptr;
    node* root = new node;
    root->data = postorder[postR];
    root->deep = deep;
    int k = inL;
    while (inorder[k] != postorder[postR]) ++k;
    root->left = create(inL, k - 1, postL, postR - 1 - (inR - k), deep + 1, root);
    root->right = create(k + 1, inR, postR - (inR - k), postR - 1, deep + 1, root);
    if ((root->left == nullptr && root->right) || (root->left && root->right == nullptr)) {
        isfull = false;
    }
    treeNode[root->data] = root;
    parent[root->data] = p;
    return root;
}

int main() {
    scanf("%d", &N);
    postorder = vector<int>(N, 0);
    inorder = vector<int>(N, 0);
    for (int i = 0; i < N; ++i) {
        scanf("%d", &postorder[i]);
    }
    for (int i = 0; i < N; ++i) {
        scanf("%d", &inorder[i]);
    }
    node *root = create(0, N - 1, 0, N - 1, 0, nullptr);
    int m;
    scanf("%d\n", &m);
    string str;
    unordered_set<int> st(postorder.begin(), postorder.end());
    for (int i = 0; i < m; ++i) {
        getline(cin, str);
        char s[50];
        strcpy(s, str.c_str());
        int a, b;
        if (str.find("root") != string::npos) {
            int a;
            sscanf(s, "%d is the root", &a);
            if (root && a == root->data) printf("Yes\n");
            else printf("No\n");
        } else if (str.find("siblings") != string::npos) {
            sscanf(s, "%d and %d are siblings", &a, &b);
            if (parent[a] && parent[b] && parent[a]->data == parent[b]->data) printf("Yes\n");
            else printf("No\n");
        } else if (str.find("parent") != string::npos) {
            sscanf(s, "%d is the parent of %d", &a, &b);
            if (parent[b] && parent[b]->data == a) printf("Yes\n");
            else printf("No\n");
        } else if (str.find("left") != string::npos) {
            sscanf(s, "%d is the left child of %d", &a, &b);
            if (treeNode[b] && treeNode[b]->left && treeNode[b]->left->data == a) printf("Yes\n");
            else printf("No\n");
        } else if (str.find("right") != string::npos) {
            sscanf(s, "%d is the right child of %d", &a, &b);
            if (treeNode[b] && treeNode[b]->right && treeNode[b]->right->data == a) printf("Yes\n");
            else printf("No\n");
        } else if (str.find("same") != string::npos) {
            sscanf(s, "%d and %d are on the same level", &a, &b);
            if (treeNode[a] && treeNode[b] && treeNode[a]->deep == treeNode[b]->deep) printf("Yes\n");
            else printf("No\n");
        } else {
            if (isfull) {
                printf("Yes\n");
            } else {
                printf("No\n");
            }
        }
    }
    return 0;
}