PAT甲级-1127 ZigZagging on a Tree

题目

题目大意

给出一棵树的中序和后序遍历，要求按层序输出这棵树，但是按照从左到右，再从右到左，再从左到右的顺序。

思路

由中序遍历和后序遍历可以构造出一棵二叉树。观察题目中要求的输出顺序，发现层数为奇数的都是逆序输出（层数从1开始），层数为偶数的顺序输出。因此构建好二叉树后，可以按照普通的层序遍历进行，只不过队列元素还需要和层数绑定，子节点的层数 = 父节点的层数 + 1。然后用一个二维数组存储各个层数的节点，需要逆序输出的层用reverse()翻转即可。

最后的输出要求不能有多余的空格，所以又加了一个res数组，存储要输出的结果。

代码

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;int n;
vector<int> in;
vector<int> post;
vector<vector<int>> v;  // 存放相同层数的节点struct node{int id;node * lchild, * rchild;int level;  // 每个节点的层数，在bfs中用
};void buildTree(node * &root, int il, int ir, int pl, int pr){if (il > ir || pl > pr){return;}root = new node();root->id = post[pr];int pos;for (int i = 0; i < n; i++){if (in[i] == root->id){pos = i;break;}}root->lchild = root->rchild = nullptr;buildTree(root->lchild, il, pos - 1, pl, pl + (pos-1-il));buildTree(root->rchild, pos + 1, ir, pl + (pos-il), pr - 1);
}void bfs(node * root){queue<node *> q;root->level = 1;q.push(root);v[root->level].push_back(root->id);while (!q.empty()){node * now = q.front();q.pop();if (now->lchild){now->lchild->level = now->level + 1;q.push(now->lchild);v[now->lchild->level].push_back(now->lchild->id);}if (now->rchild){now->rchild->level = now->level + 1;q.push(now->rchild);v[now->rchild->level].push_back(now->rchild->id);}}
}int main(){cin >> n;in.resize(n);post.resize(n);v.resize(n + 1);for (int i = 0; i < n; i++){cin >> in[i];}for (int i = 0; i < n; i++){cin >> post[i];}node * root = nullptr;buildTree(root, 0, n - 1, 0, n - 1);bfs(root);vector<int> res;for (int i = 1; i <= n; i++){if ((int)v[i].size() == 0){break;}if (i % 2 == 1){reverse(v[i].begin(), v[i].end());}  // 第奇数层是逆序for (int j = 0; j < (int)v[i].size(); j++){res.push_back(v[i][j]);}}for (int i = 0; i < (int)res.size(); i++){cout << res[i];if (i != (int)res.size() - 1){cout << " ";}}cout << endl;return 0;
}