PAT 二叉树的各种查询操作

string和char数组的不熟悉,导致调试了2h

错误做法

string str;
char ss[50];
for(int i = 0; i < str.size(); i++) ss[i] = str[i]; 千万不能自己这样做

正确做法,用str.c_str()

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.

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

OutPut:
Yes
No
Yes
No
Yes
Yes
Yes

易错点:将string一个个字符copy到数组中

满分代码

/**
难度: 后序和中序构建一棵树
同时
1存储兄弟节点
2是都有两个孩子节点(full tree)
3是否为根节点
4是否同一个层级
5父节点
6孩子节点

读取数据的方式:sscnaf 和 sprintf

*/
#include <iostream>
#include <cstring>
#include <unordered_map>
using namespace std;
const int N = 40;
int in[N], post[N], l[N], r[N], dp[N], siblin[N];
bool is_full = true;
int build(int il, int ir, int pl, int pr, int dep)
{
    if (il > ir) return -1;
    int root = post[pr];
    int k = root, lchild = -1, rchild =-1;
    if (k >= il) lchild = build(il, k - 1, pl, pl + (k - il - 1), dep + 1);
    if (k <= ir) rchild = build(k + 1, ir, pl + (k - il - 1) + 1, pr - 1, dep + 1);
    if (lchild == -1 && rchild != -1) is_full = false;
    if (lchild != -1 && rchild == -1) is_full = false;
    if (lchild != -1 && rchild != -1) siblin[lchild] = rchild, siblin[rchild] = lchild;
    // 最难的一部分,理清怎么来存dep
    dp[root] = dep;
    l[root] = lchild;
    r[root] = rchild;
    return root;
}
int main()
{
    int m, n;
    cin >> m;
    memset(l, -1, sizeof l);
    memset(r, -1, sizeof r);
    memset(siblin, 0x3f, sizeof siblin);
    memset(dp, 0x3f, sizeof dp);
    unordered_map<int, int> pos;
    for(int i = 0; i < m; i++) cin >> post[i];
    int root  = post[m - 1];
    for(int i = 0; i < m; i++)
    {
        cin >> in[i];
        pos[in[i]] = i;
    }
    // 这一步很难呀,构建映射, 数值从0-m重新构建
    for(int i = 0; i < m; i++) post[i] = pos[post[i]];

    build(0, m - 1, 0, m - 1, 0);

    cin >> n;
    getchar();
    while (n --)
    {
        string str;
        int x, y;
        getline(cin, str);
        //for(int i = 0; i < str.size(); i++) ss[i] = str[i];  千万不能自己这样做
        if (str.find("root") != string::npos)
        {
            sscanf(str.c_str(), "%d is the root", &x);
            if (x == root) printf("Yes\n");
            else printf("No\n");
        }else if (str.find("siblings") != string::npos)
        {
            sscanf(str.c_str(), "%d and %d are siblings", &x, &y);
            x = pos[x], y = pos[y];
            if (siblin[x] != y) printf("No\n");
            else printf("Yes\n");
        }else if (str.find("parent") != string::npos)
        {
            sscanf(str.c_str(), "%d is the parent of %d", &x, &y);
            y = pos[y], x = pos[x];
            if (l[x] == y || r[x] == y) printf("Yes\n");
            else printf("No\n");
        }else if (str.find("left child") != string::npos)
        {
            sscanf(str.c_str(), "%d is the left child of %d", &x, &y);
            x = pos[x], y = pos[y];
            if (l[y] != x) printf("No\n");
            else printf("Yes\n");
        }else if (str.find("right child") != string::npos)
        {
            sscanf(str.c_str(), "%d is the right child of %d", &x, &y);
            x = pos[x], y = pos[y];
            if (r[y] != x) printf("No\n");
            else printf("Yes\n");
        }else if (str.find("same level") != string::npos)
        {
            sscanf(str.c_str(), "%d and %d are on the same level", &x, &y);
            x = pos[x], y = pos[y];
            if (dp[x] == dp[y]) printf("Yes\n");
            else printf("No\n");
        }else if (str.find("full") != string::npos)
        {
            if (is_full) printf("Yes\n");
            else printf("No\n");
        }
    }
}

27分代码

#include <iostream>
#include <cstring>
#include <unordered_map>
#include <string.h>
using namespace std;

const int N = 40;
int post[N], in[N], l[N], r[N] ,d[N], p[N], sib[N];
unordered_map<int,int> pos;
bool flag = true;
int build(int il, int ir, int postl, int postr, int dep)
{
    int root = post[postr];
    d[root] = dep;
    int k = root;
    int left, right;
    bool f1 = false, f2 = false;
    if (k > il)
    {
        left = build(il, k - 1, postl, postl + (k - il - 1), dep + 1);
        l[root] = left;
        p[left] = root;
        f1 = true;
    };
    if (k < ir)
    {
        right = build(k + 1, ir, postl + (k - il - 1) + 1, postr - 1, dep + 1);
        r[root] = right;
        p[right] = root;
        f2 = true;
    }
    if (f1 && f2)
    {
        sib[left] = right;
        sib[right] = left;
    }else if (!f1 && !f2){}
    else flag = false;

    return root;
}
int main()
{
    int m, n;
    cin >> m;
    memset(l, -1, sizeof l);
    memset(r, -1, sizeof r);
    memset(p, -1, sizeof p);
    memset(sib, -1, sizeof sib);
    for(int i = 0; i < m; i++) cin >> post[i];
    int root = post[m - 1];
    for(int i = 0; i < m; i++)
    {
        cin >> in[i];
        pos[in[i]] = i;
    }
    for(int i = 0; i < m; i++) post[i] = pos[post[i]];
    build(0, m - 1, 0, m - 1, 1);

    cin >> n;
    getchar();// 吸收换行
    while (n --)
    {
        string str;

        //cin >> str;
        char sstr[30];
        // 一定要用getline, cin只能读一个字符
        getline(cin , str);
        int x, y;
        for(int i = 0; i < str.size(); i++) sstr[i] = str[i];
        if (str.find("root") != string::npos)
        {
            // 要用&符号,漏了会报错
            sscanf(sstr, "%d is the root", &x);
            if (x == root) printf("Yes\n");
            else printf("No\n");
        }else if(str.find("siblings") != string::npos)
        {

            sscanf(sstr, "%d and %d are siblings", &x, &y);
            x = pos[x], y = pos[y];
            if (sib[x] == y) printf("Yes\n");
            else printf("No\n");
        }else if (str.find("parent") != string::npos)
        {
            sscanf(sstr, "%d is the parent of %d", &x, &y);
            x = pos[x], y = pos[y];
            if (p[y] == x) printf("Yes\n");
            else printf("No\n");
        }else if (str.find("left") != string::npos)
        {
            sscanf(sstr, "%d is the left child of %d", &x, &y);
            x = pos[x], y = pos[y];
            if (l[y] == x) printf("Yes\n");
            else printf("No\n");
        }
        else if (str.find("right") != string::npos)
        {
            sscanf(sstr, "%d is the right child of %d", &x, &y);
            x = pos[x], y = pos[y];
            if (r[y] == x) printf("Yes\n");
            else printf("No\n");
        }
        else if (str.find("level") != string::npos)
        {
            sscanf(sstr, "%d and %d are on the same level", &x, &y);
            x = pos[x], y = pos[y];
            if (d[x] == d[y]) printf("Yes\n");
            else printf("No\n");
        }
        else if (str.find("full") != string::npos)
        {

            if (flag) printf("Yes\n");
            else printf("No\n");
        }
    }
}

方案二 23分代码

#include <iostream>
#include <cstring>
#include <unordered_map>
using namespace std;

const int N = 40;
int l[N], r[N], p[N], in[N], post[N], d[N];
unordered_map<int, int> pos;
int m, n;
bool full_tree = true;
int build (int il, int ir, int postl, int postr, int deep)
{
    int root = post[postr];
    int k = root;
    d[root] = deep;
    bool f1 = false, f2 = false;
    if (k > il)
    {
        l[root] = build(il, k - 1, postl, postl + (k - il - 1), deep + 1);
        p[l[root]] = root;
        f1 = true;
    }
    if (k < ir)
    {
        r[root] = build(k + 1, ir, postl + (k - il - 1) + 1, postr - 1, deep + 1);
        p[r[root]] = root;
        f2 = true;
    }
    if (f1 && !f2) full_tree = false;
    else if (f2 && !f1) full_tree = false;
    return root;
}

void check(string str)
{
    char sstr[30];
    for(int i = 0; i < str.size(); i++) sstr[i] = str[i];
    bool flag = false;
    int x, y;
    if (str.find("root") != string::npos)
    {
        sscanf(sstr, "%d is the root", &x);
        int u = in[post[m - 1]];
        if (u == x) flag = true;
    }else if (str.find("siblings") != string::npos)
    {
        sscanf(sstr, "%d and %d are siblings", &x, &y);
        x = pos[x];
        y = pos[y];
        if (p[x] == p[y]) flag = true;
    }else if (str.find("parent") != string::npos)
    {
        sscanf(sstr, "%d is the parent of %d", &x, &y);
        x = pos[x], y = pos[y];
        if (x == p[y]) flag = true;
    }else if (str.find("left") != string::npos)
    {
        sscanf(sstr, "%d is the left child of %d", &x, &y);
        x = pos[x], y = pos[y];
        if (l[y] == x) flag = true;
    }else if (str.find("right") != string::npos)
    {
        sscanf(sstr, "%d is the right child of %d", &x, &y);
        x = pos[x], y = pos[y];
        if (r[y] == x) flag = true;
    }else if (str.find("level") != string::npos)
    {
        sscanf(sstr, "%d and %d are on the same level", &x, &y);
        x = pos[x], y = pos[y];
        if (d[x] == d[y]) flag = true;
    }else if (str.find("full") != string::npos)
    {
        if (full_tree) flag = true;
    }
    if (flag) printf("Yes\n");
    else printf("No\n");
}
int main()
{
    cin >> m;
    for(int i = 0; i < m; i++) cin >> post[i];
    for(int i = 0; i < m; i++)
    {
        cin >> in[i];
        pos[in[i]] = i;
    }
    for(int i = 0; i < m; i++) post[i] = pos[post[i]];
    build(0, m - 1, 0, m - 1, 1);
    cin >> n;
    getchar();
    while (n --)
    {
        string str;
        getline(cin, str);
        check(str);
    }
}