PAT-1127 ZigZagging on a Tree

AXV

发个题解，记录下做题的过程
这道题层序遍历，每层换下顺序就可

[C++] 纯文本查看 复制代码

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <queue>

using namespace std;
int n;
int in[60];
int post[60];
vector<int> levs[100];

void tran(int head, int tail, int level)
{
    if (head == tail) {
        levs[level].push_back(in[head]);
        return;
    }

    int rid = -1;

    for (int i = 0; i < n; i++) {
        int pnum = post[i];
        for (int j = head; j <= tail; j++) {
            if (pnum == in[j]) {
                rid = j;
                break;
            }
        }
        if (rid != -1) {
            break;
        }
    }

    if (rid > head) {
        tran(head, rid - 1, level + 1);
    }
    levs[level].push_back(in[rid]);
    if (rid < tail) {
        tran(rid + 1, tail, level + 1);
    }
}

int main(void)
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", in + i);
    }
    for (int i = 0; i < n; i++) {
        scanf("%d", post + i);
    }

    reverse(post, post + n);

    tran(0, n - 1, 0);
    printf("%d", levs[0][0]);
    bool ltr = true;
    for (int i = 1; i < n; i++) {
        if (ltr) {
            for (int j = 0; j < levs[i].size(); j++) {
                printf(" %d", levs[i][j]);
            }
            ltr = false;
        } else {
            for (int j = levs[i].size() - 1; j >= 0; j--) {
                printf(" %d", levs[i][j]);
            }
            ltr = true;
        }
    }
}

vethenc

加油！努力刷题，定有所得。