哎呀,气死我了,一晃眼以为全是字符串操作,一顿哈希建树操作,emmm....,最后写完了提交,全错,又回来继续看题

原来左右孩子都是用下标表示,不是字符串,然后五分钟重写了一个一次过了,嗨呀,气死我了

这道题就是递归左右子树得到左右子树的中缀表达式,然后(left+root+right)就可以啦,注意判断根节点不用取括号

如果是最后一层的节点也不加括号

正确代码:

#include<iostream>
#include<string>
#include<map>
#include<set>
#include<algorithm>
#include<queue>
#include<cmath>
#include<string.h>
#include<unordered_map>
#include<unordered_set>
using namespace std;
#define INT_MIN -2147483648
#define INT_MAX 2147483647
int read() {
    char p;
    while ((p = getchar()) < '0' || p > '9');
    int sum = p - 48;
    while ((p = getchar()) >= '0' && p <= '9')sum = sum * 10 + p - '0';
    return sum;
}
const int maxn = 100;
string val[maxn];
int tree[maxn][2];
bool notroot[maxn];
int n;
int root;
string dfs(int rt) {
    if (rt == -1)return "";
    if (tree[rt][0] == -1 && tree[rt][1] == -1) {//无子树不要加括号直接返回
        return val[rt];
    }
    string ls = dfs(tree[rt][0]);
    string rs = dfs(tree[rt][1]);
    if (rt != root) {//不是更节点要加括号
        return '(' + ls + val[rt] + rs + ')';
    }
    else {
        return ls + val[rt] + rs;
    }
}
int main() {
    //freopen("test.txt", "r", stdin);
    n = read();
    for (int i = 1; i <= n; i++) {
        string fa;
        cin >> fa;
        val[i] = fa;//保存节点数据
        int ls, rs;
        scanf("%d%d", &ls, &rs);
        tree[i][0] = ls;
        tree[i][1] = rs;
        notroot[ls] = 1;
        notroot[rs] = 1;
    }
    for (int i = 1; i <= n; i++) {
        if (!notroot[i]) {
            root = i;break;
        }
    }
    string res=dfs(root);
    cout << res << endl;
    return 0;
}

View Code

我的瞎操作:

#include<iostream>
#include<string>
#include<map>
#include<set>
#include<algorithm>
#include<queue>
#include<cmath>
#include<string.h>
#include<unordered_map>
#include<unordered_set>
using namespace std;
#define INT_MIN -2147483648
#define INT_MAX 2147483647
int read() {
    char p;
    while ((p = getchar()) < '0' || p > '9');
    int sum = p - 48;
    while ((p = getchar()) >= '0' && p <= '9')sum = sum * 10 + p - '0';
    return sum;
}
const int maxn = 100;
string val[maxn];
int tot=0;
int tree[maxn][2];
unordered_map<string, int>M;
int notroot[maxn];
int n;
int root = -1;
string dfs(int rt) {
    if (rt == -1)return "";
    if (tree[rt][0] == -1 && tree[rt][1] == -1) {
        return val[rt];
    }
    string ls = dfs(tree[rt][0]);
    string rs = dfs(tree[rt][1]);
    //cout << val[rt] << endl;
    if(rt!=root)return '(' + ls + val[rt] + rs + ')';
    else return  ls + val[rt] + rs;
}
int main() {
    //freopen("test.txt", "r", stdin);
    n = read();
    for (int i = 1; i <= n; i++) {
        string fa, l, r;
        cin >> fa >> l >> r;
        bool flg1 = (l != "-1"), flg2 = (r != "-1");
        //cout << flg1 <<" "<< flg2 << endl;
        if (!M.count(fa)) {
            M[fa] = ++tot;
            val[tot] = fa;
        }
        if (flg1&&!M.count(l)) {
            M[l] = ++tot;
            notroot[tot] = 1;
            val[tot] = l;
        }
        if (flg2&&!M.count(r)) {
            M[r] = ++tot;
            notroot[tot] = 1;
            val[tot] = r;
        }
        int rt = M[fa];
        if (flg1) {
            //cout << M[l] << endl;
            tree[rt][0] = M[l];
        }
        else {
            tree[rt][0] = -1;
        }
        if (flg2) {
            //cout << M[r] << endl;
            tree[rt][1] = M[r];
        }
        else {
            tree[rt][1] = -1;
        }
    }
    for (int i = 1; i <= tot; i++) {
        if (!notroot[i]) {
            root = i; break;
        }
    }
    //cout << root << endl;
    string res=dfs(root);
    cout << res << endl;
    return 0;
}

View Code