『1159』Structure of a Binary Tree

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

---

Ω

给出一棵二叉树的后序、中序遍历，然后判断七种陈述模式的对错。

树的节点不超过30个，因此直接搞个结构体存储所有信息——父节点、子节点、深度。而且节点编号不会超过1000，因此直接开个数组存储所有节点的结构体。在递归建树的过程中，记录每个节点的信息，同时如果当前节点只有一个孩子则标记notFull为true。

另一个难点是判断陈述模式，我们可以先将整行读入(⚠️不要忘记读完 后getchar())，然后按照空格将单词压入数组中，根据语句中的关键词进行判断。⚠️判断顺序尽量按照单词数少的模式到单词数多的模式，如果先判断单词数多模式偏后的关键词可能会导致单词数少模式的越界访问。

---



#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
vector<int> post, in;
bool notFull = false, ans;

struct node
{
    int parent = -1, depth = 0;
    pair<int, int> sons{-1, -1};
};

vector<node> tree(1001);

void build(int ps, int pe, int is, int ie)
{
    int bias = find(in.begin() + is, in.begin() + ie, post[pe]) - in.begin() - is;
    if (bias > 0)
    {
        tree[post[pe]].sons.first = post[ps + bias - 1];
        tree[post[ps + bias - 1]].parent = post[pe];
        tree[post[ps + bias - 1]].depth = tree[post[pe]].depth + 1;
        build(ps, ps + bias - 1, is, is + bias);
    }
    if (is + bias < ie - 1)
    {
        tree[post[pe]].sons.second = post[pe - 1];
        tree[post[pe - 1]].parent = post[pe];
        tree[post[pe - 1]].depth = tree[post[pe]].depth + 1;
        build(ps + bias, pe - 1, is + bias + 1, ie);
    }
    notFull |= (bias < ie - is - 1) ^ (bias > 0);
}

int main()
{
    int n, m, p = 0;
    cin >> n;
    post.resize(n), in.resize(n);
    for (auto &k: post) cin >> k;
    for (auto &k: in) cin >> k;
    build(0, n - 1, 0, n);
    cin >> m;
    getchar();
    string st;
    for (int i = 0; i < m; ++i, p = 0)
    {
        vector<string> jdg;
        getline(cin, st);
        st.push_back(' ');
        for (int j = 0; j < st.size(); ++j)
            if (st[j] == ' ')
            {
                jdg.push_back(st.substr(p, j - p));
                p = j + 1;
            }
        if (jdg[3] == "root") ans = stoi(jdg[0]) == post.back();
        else if (jdg[0] == "It") ans = !notFull;
        else if (jdg[1] == "and")
        {
            auto &a = tree[stoi(jdg[0])], &b = tree[stoi(jdg[2])];
            ans = (jdg[4] == "on" ? a.depth == b.depth : a.parent == b.parent);
        }
        else if (jdg[3] == "parent") ans = stoi(jdg[0]) == tree[stoi(jdg[5])].parent;
        else
            ans = (jdg[3] == "left" ? tree[stoi(jdg.back())].sons.first == stoi(jdg[0]) :
                   tree[stoi(jdg.back())].sons.second == stoi(jdg[0]));
        printf("%s\n", ans ? "Yes" : "No");
    }
}