1127. ZigZagging on a Tree (30)
Suppose that all the keys in a binary tree are distinct positive integers. A unique binary tree can be determined by a given pair of postorder and inorder traversal sequences. And it is a simple standard routine to print the numbers in level-order. However, if you think the problem is too simple, then you are too naive. This time you are supposed to print the numbers in "zigzagging order" -- that is, starting from the root, print the numbers level-by-level, alternating between left to right and right to left. For example, for the following tree you must output: 1 11 5 8 17 12 20 15.
Input Specification:
Each input file contains one test case. For each case, the first line gives a positive integer N (<= 30), the total number of nodes in the binary tree. The second line gives the inorder sequence and the third line gives the postorder sequence. All the numbers in a line are separated by a space.
Output Specification:
For each test case, print the zigzagging sequence of the tree in a line. All the numbers in a line must be separated by exactly one space, and there must be no extra space at the end of the line.
Sample Input:
8
12 11 20 17 1 15 8 5
12 20 17 11 15 8 5 1
Sample Output:
1 11 5 8 17 12 20 15 题意：通过后序遍历中序遍历复原二叉树，再按照题目要求的顺序输出，输出要求只要对层序遍历的方式稍加改动即可。
AC代码：
#define _CRT_SECURE_NO_DEPRECATE
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
#include<set>
#include<queue>
#include<map>
using namespace std;
#define INF 0x3f3f3f
#define N_MAX 30000+5
typedef long long ll;
struct Node {
int key=INF, L, R;
Node() {}
Node(int key,int l,int r):key(key),L(l),R(r) {}
}node[N_MAX]; vector<int> in, post;int n, cnt;
void dfs(int n,int l,int r) {
if (l>r) {
node[n].key = INF;
return;
}
int root = post[cnt--];
node[n] = Node(root, * n+, * n + );
int k = find(in.begin(),in.end(),root)-in.begin();
dfs( * n + , k + , r);
dfs( * n+, l, k - );
}
int order[N_MAX];
vector<int>res; vector<int>level;
void bfs(int root) {
queue<int>que;
que.push(root);
order[root] = ;
while (!que.empty()) {
int p = que.front(); que.pop();
if (node[p].key != INF) {
res.push_back(node[p].key);
level.push_back(order[p]);
if (node[p].L != ) { order[node[p].L] = order[p] + ;que.push(node[p].L); }
if (node[p].R != ) { order[node[p].R] = order[p] + ;que.push(node[p].R); }
}
}
} int main() {
while (scanf("%d",&n)!=EOF) {
in.resize(n); post.resize(n);
for (int i = ; i < n; i++)scanf("%d",&in[i]);
for (int i = ; i < n; i++)scanf("%d", &post[i]);
cnt = n - ;
dfs(, , n - );
bfs();
int num = ,orde=;//num是每一层的计数器
vector<int>out;
for (int i = ; i < res.size();) {
out.clear();
while (i<res.size()&&orde ==level[i]) {
out.push_back(res[i]);
i++;
}
if (orde & ) {
for (int j = ; j < out.size(); j++)printf("%d%s", out[j], (i == res.size()&&j+==out.size())? "\n" : " ");
}
else {
for (int j = out.size() - ; j >= ; j--)printf("%d%s", out[j], (i == res.size()&&j== )? "\n" : " ");
}
orde++;
} }
}