不务正业系列之pat解题: 1119. Pre- and Post-order Traversals (30)

[yooocen]

第一种方法是我写的，有两个用例段错误

#include <cstdio>
#include <vector>
using namespace std;
vector<int> ans;
int *pre, *post;
static bool  i_unique = true;

int searchPosInPreOrder (int postIndex) {
    for (int i = 0; i <= sizeof(pre) ; i++) {
        if (postIndex == pre[i]) {
            return i;
        }
    }
    return -1;
}
int searchPreInPosOrder (int preIndex) {
    for (int i = 0; i <= sizeof(post) ; i++) {
        if (preIndex == post[i]) {
            return i;
        }
    }
    return -1;
}

void buildInOrderSequence(int preF , int preE , int postF , int postE){
    if(preF >= preE){
        ans.push_back(*(pre+preF)) ;
        return;
    }

    int l_newPreF = preF+1;
    int l_newPreE = searchPosInPreOrder(*(post+ postE-1))-1;

    int l_newPostF = postF;
    int l_newPostE = searchPreInPosOrder(*(pre+ preF+1));
    if(*(pre+ preF+1)==*(post+postE-1)){
        i_unique =false;

    } else {
        buildInOrderSequence(l_newPreF, l_newPreE, l_newPostF, l_newPostE);
    }
    ans.push_back(*(pre+preF));

    int r_newPreF = searchPosInPreOrder(*(post+postE-1));
    int r_newPreE = preE;

    int r_newPostF = searchPreInPosOrder(*(pre+preF+1))+1;
    int r_newPostE = postE-1;

    buildInOrderSequence(r_newPreF,r_newPreE,r_newPostF,r_newPostE);

}

int main() {
    int n = 0;
    scanf("%d", &n);
    pre = new int [n];
    post = new int [n];
    for (int i = 0; i < n; i++) {
        scanf("%d", &pre[i]);
    }
    for (int i = 0; i < n; i++) {
        scanf("%d", &post[i]);
    }
    buildInOrderSequence(0, n - 1, 0, n - 1);
    printf("%s\n", i_unique ? "Yes" : "No");
    printf("%d", ans[0]);
    for (int i = 1; i < ans.size(); i++) {
        printf(" %d", ans[i]);
    }
    printf("\n");
    return 0;
}

第二个是网上某高人写的

#include <cstdio>
#include <vector>
using namespace std;
vector<int> ans;
int *pre, *post, unique = 1;

int findFromPre (int x, int l, int r) {
    for (int i = l; i <= r; i++) {
        if (x == pre[i]) {
            return i;
        }
    }
    return -1;
}

void setIn (int prel, int prer, int postl, int postr) {
    if (prel == prer) {
        ans.push_back(pre[prel]);
        return;
    }
    if (pre[prel] == post[postr]) {
        int x = findFromPre(post[postr - 1], prel + 1, prer);
        if (x - prel > 1) {
            setIn(prel + 1, x - 1, postl, postl + x - prel - 2);
            ans.push_back(post[postr]);
            setIn(x, prer, postl + x - prel - 2 + 1, postr - 1);
        } else {
            unique = 0;
            ans.push_back(post[postr]);
            setIn(x, prer, postl + x - prel - 2 + 1, postr - 1);
        }
    }
}

int main() {
    int n = 0;
    scanf("%d", &n);
    pre = new int [n];
    post = new int [n];
    for (int i = 0; i < n; i++) {
        scanf("%d", &pre[i]);
    }
    for (int i = 0; i < n; i++) {
        scanf("%d", &post[i]);
    }
    setIn(0, n - 1, 0, n - 1);
    printf("%s\n", unique ? "Yes" : "No");
    printf("%d", ans[0]);
    for (int i = 1; i < ans.size(); i++) {
        printf(" %d", ans[i]);
    }
    printf("\n");
    return 0;
}