[C++知识库]PAT A1159 Structure of a Binary Tree测试点3答案错误？

原题链接

测试点3

这道题，测试点3，真坑。但是我试出来为什么错误了。因为测试点3里面有一个陈述，关于谁是谁的父亲的陈述，这个陈述里面，两个数的值是相同的。类似于“A is the parent of A”，这时候，应该是错误，但是如果代码没有检测两个数是否相同，则可能出错。

注意

以及关于siblings的判断，也应该首先判断是否两个数相同。
只有当两个值不同、两个值不在同一层、两个值的父亲节点地址相同，siblings陈述才正确。

AC代码：

#include <bits/stdc++.h>

using namespace std;

struct node {
    int val, depth;
    node *lchild, *rchild, *father;
    node () {}
    node (int v) : val(v), lchild(nullptr), rchild(nullptr), father(nullptr) {}
};

int n, m;
int post[50];
int ino[50];
bool full = true;
unordered_map<int, int> pos;
unordered_map<int, node*> mp;

node* create(int postl, int postr,int inl, int inr, int depth, node* fa) {
    if (postl > postr) return nullptr;
    node* root = new node(post[postr]);
    mp[root->val] = root;
    root->father = fa;
    root->depth = depth;
    int k = pos[post[postr]], cnt = k - inl;
    root->lchild = create(postl, postl + cnt - 1, inl, k - 1, depth + 1, root);
    root->rchild = create(postl + cnt, postr - 1, k + 1, inr, depth + 1, root);

    if (root->lchild && !root->rchild) full = false;
    else if (root->rchild && !root->lchild) full = false;

    return root;
}

int main()
{
    scanf("%d", &n);
    for (int i = 0;i < n;i++) scanf("%d", &post[i]);
    for (int i = 0;i < n;i++) {
        scanf("%d", &ino[i]);
        pos[ino[i]] = i;
    }

    node* root = create(0, n-1, 0, n-1, 0, nullptr);
    root->father = root;

    scanf("%d ", &m);
    for (int r = 0;r < m;r++) {
        string temp;
        getline(cin, temp);
        if (temp.find("root") != string::npos) {
            int u;
            sscanf(temp.c_str(), "%d is the root", &u);
            if (root->val == u) printf("Yes\n");
            else printf("No\n");
        } else if (temp.find("siblings") != string::npos) {
            int u, v;
            sscanf(temp.c_str(), "%d and %d are siblings", &u, &v);
            if (u != v && mp[u]->depth == mp[v]->depth && mp[u]->father == mp[v]->father) {
                // 先判断两个数是否相同
                printf("Yes\n");
            } else printf("No\n");
        } else if(temp.find("parent") != string::npos) {
            int u, v;
            sscanf(temp.c_str(), "%d is the parent of %d", &u, &v);
            
            if (u != v && mp[v]->father == mp[u]) printf("Yes\n"); // 先判断两个数是否相同
            else printf("No\n");
        } else if (temp.find("left") != string::npos) {
            int u, v;
            sscanf(temp.c_str(), "%d is the left child of %d", &u, &v);
            if (mp[v]->lchild == mp[u]) printf("Yes\n");
            else printf("No\n");
        } else if (temp.find("right") != string::npos) {
            int u, v;
            sscanf(temp.c_str(), "%d is the right child of %d", &u, &v);
            if (mp[v]->rchild == mp[u]) printf("Yes\n");
            else printf("No\n");
        } else if (temp.find("level") != string::npos) {
            int u, v;
            sscanf(temp.c_str(), "%d and %d are on the same level", &u, &v);
            if (mp[u]->depth == mp[v]->depth) printf("Yes\n");
            else printf("No\n");
        } else {
            if (full) printf("Yes\n");
            else printf("No\n");
        }
    }

    return 0;
}