自己测试的案例正确,但结果都是WA
查看原帖
自己测试的案例正确,但结果都是WA
698372
tgsalgo楼主2022/3/19 17:16
/* https://www.luogu.com.cn/problem/P1827 */
#include <cstdio>

char preOrder[26], inOrder[26];

// 中序遍历序列中根元素位置
int root(char c, int il, int ir) {
    int r = il;
    while (r <= ir && inOrder[r] != c)
        r++;
    return r;
}

void slove(int pl, int pr, int il, int ir) {
    if (pl > pr || il > ir) return;
    if (pl == pr) {
        printf("%c", preOrder[pl]);
        return;
    }
    char c = preOrder[pl];
    int r = root(c, il, ir);
    int ls = r - il, rs = ir - r; // 左右子树元素个数
    slove(pl + 1, pl + ls, il, r - 1); // 左子树
    slove(pl + ls + 1, pr, r + 1, ir); // 右子树
    printf("%c", c);
}

int main() {
    int n = 0;
    char c;
    while ((c = getchar()) != '\n')
        inOrder[n++] = c;
    for (int i = 0; i < n; i++)
        scanf("%c", &preOrder[i]);

    slove(0, n-1, 0, n-1);
    
    return 0;
}
2022/3/19 17:16
加载中...