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 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 <string>
#include <algorithm>

using namespace std;

const int N = 30 + 10;
int in[N], post[N];
unordered_map <int, int > l, r;
unordered_map <int, int > pos, parent, depth;
int n, m, root;
bool is_full;

int build(int il, int ir, int pl, int pr, int d)
{
    int root = post[pr];
    depth[root] = d;
    int k = pos[root];
    if(k < ir) 
    {
        int son = build(k + 1, ir, pr - 1 - (ir - (k + 1)), pr - 1, d + 1);
        r[root] = son;
        parent[son] = root;
    }
    if(k > il)
    {
        int son = build(il, k - 1, pl, pl + k - 1 - il, d + 1);
        l[root] = son;
        parent[son] = root;
    }
    return root;
}

bool check (string s)
{
    if(s.find("root") != string::npos)
    {
        int rt = stoi(s.substr(0, s.find(" ")));
        if(rt == root) return true;
        return false;
    }else if(s.find("siblings") != string::npos){
        int a = stoi(s.substr(0, s.find(" ")));
        int pos = s.find("d") + 2;
        int len = s.find("are") - pos - 1;
        int b = stoi(s.substr(pos, len));
        if(parent.count(a) && parent.count(b))
            if(parent[a] == parent[b]) return true;
        return false;
    }else if(s.find("parent") != string::npos){
        int id = stoi(s.substr(0, s.find(" ")));
        reverse(s.begin(), s.end());
        string tmp = s.substr(0, s.find(" "));
        reverse(tmp.begin(), tmp.end());
        int son = stoi(tmp);
        if(parent.count(son))
            if(parent[son] == id) return true;
        return false;
    }else if(s.find("left") != string::npos){
        int id = stoi(s.substr(0, s.find(" ")));
        reverse(s.begin(), s.end());
        string tmp = s.substr(0, s.find(" "));
        reverse(tmp.begin(), tmp.end());
        int son = stoi(tmp);
        if(l.count(son))
            if(l[son] == id) return true;
        return false;
    }else if(s.find("right") != string::npos){
        int id = stoi(s.substr(0, s.find(" ")));
        reverse(s.begin(), s.end());
        string tmp = s.substr(0, s.find(" "));
        reverse(tmp.begin(), tmp.end());
        int son = stoi(tmp);
        if(r.count(son))
            if(r[son] == id) return true;
        return false;
    }else if(s.find("same") != string::npos){
        int a = stoi(s.substr(0, s.find(" ")));
        int pos = s.find("d") + 2;
        int len = s.find("are") - pos - 1;
        int b = stoi(s.substr(pos, len));
        if(depth.count(a) && depth.count(b))
            if(depth[a] == depth[b]) return true;
        return false;
    }else if(s.find("full") != string::npos){
         if(is_full) return true;
         return false;
    }
}

bool dfs(int root)
{
    if((!l.count(root) && r.count(root)) || (!r.count(root) && l.count(root)))
            return false;
    bool res1 = true, res2 = true;
    if(l.count(root)) res1 = dfs(l[root]);
    if(r.count(root)) res2 = dfs(r[root]);
    return res1 &&  res2;
}

int main()
{
    cin >> n;
    for(int i = 0; i < n; i ++) cin >> post[i];
    for(int i = 0; i < n; i ++) 
    {
        cin >> in[i];
        pos[in[i]] = i;
    }
    root = build(0, n - 1, 0, n - 1, 0);
    is_full = dfs(root);
    cin >> m;
    getchar();
    while(m --)
    {
        string s;
        getline(cin, s);
        if(check(s)) puts("Yes");
        else puts("No");
    }
    return 0;

}