PAT(Advanced Level)A1127. ZigZagging on a Tree

题意

输出一个树的层序遍历，要求每一层都调转方向

思路

• 首先是根据中序序列和后序序列建树，这是常规操作
• 用层序遍历，每次取出一层的结点，每到下一层都要调转方向一次

代码

#include <iostream>
#include <algorithm>
#include <vector>
#include <unordered_map>
#include <set>
#include <string.h>
#include <queue>
using namespace std;
vector<int> post, in, ans;
int direction = 1;
struct node {
    int val;
    struct node* left;
    struct node* right;
    node(int v): val(v), left(NULL), right(NULL){}
};

// 建树
node* build_tree(int inL, int inR, int posL, int posR) {
    if(inL > inR)   return NULL;
    node* root = new node(post[posR]);
    int pos = inL;
    while(in[pos] != post[posR])    pos++;
    int num_left = pos - inL;
    root->left = build_tree(inL, pos - 1, posL, posL + num_left - 1);
    root->right = build_tree(pos + 1, inR, posL + num_left, posR - 1);
    return root;
}
// 层序遍历
void bfs(node* root) {
    queue<node*> q;
    q.push(root);
    while(!q.empty()) {
        int len = q.size();
        vector<int> tmp;
        // 一次拿出一层的结点数
        for(int i = 0; i < len; i++) {
            auto it = q.front();
            q.pop();
            if(it->left)    q.push(it->left);
            if(it->right)   q.push(it->right);
            tmp.emplace_back(it->val);
        }
        // 调转方向
        if(direction != 0) {
            direction = 0;
            reverse(tmp.begin(), tmp.end());
        }else
            direction = 1;
        for(auto it: tmp)   ans.emplace_back(it);
    }
}
int main() {
    int N;
    cin >> N;
    post.resize(N); in.resize(N);
    for(int i = 0; i < N; i++)  cin >> in[i];
    for(int i = 0; i < N; i++)  cin >> post[i];
    node* root = build_tree(0, N - 1, 0, N - 1);
    bfs(root);
    cout << ans.front();
    for(int i = 1; i < N; i++)  cout << " " << ans[i];
    return 0;
}