PAT-A 真题 – 1127 ZigZagging on a Tree

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 ( $\leq$ 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

题目大意：给定二叉树的后序遍历序列和中序遍历序列，然后输出ZigZagging序列？？？？

ZigZagging这是什么玩意。。。

看Sample，大概知道了，是一种特殊的层序遍历，根节点正常输出，接着第一层正常层序，第二层要从右到左的输出，第三层正常，第四层又反过来。。。

这道题很有趣，解决方法是按照层，将每一层的正常层序序列存放到相应的容器中，然后隔一个一翻转就好了。

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdio>
using namespace std;
const int maxn = 31;
int in[maxn], post[maxn];
vector<vector<int> > layer(maxn);
struct node{
  int data, layer;
  node *lchild, *rchild;
};

int find_in(int n){
  for(int i = 0; i < maxn; i++)
    if(in[i] == n)
      return i;
}

node* Create(int postL, int postR, int inL, int inR){
  if(postL > postR || inL > inR) return NULL;
  node *root = new node;
  root->data = post[postR];
  int root_position = find_in(root->data),
    lchild_length = root_position - inL; 
  int lchildPostL = postL,
    lchildPostR = postL + lchild_length - 1,
    lchildInL = inL,
    lchildInR = root_position - 1;
  root->lchild = Create(lchildPostL, lchildPostR, lchildInL, lchildInR);
  int rchildPostL = lchildPostR + 1,
    rchildPostR = postR - 1,
    rchildInL = root_position + 1,
    rchildInR = inR;
  root->rchild = Create(rchildPostL, rchildPostR, rchildInL, rchildInR);
  return root;
}

void BFS(node *root){
  queue<node*> Q;
  root->layer = 0;
  Q.push(root);
  while(!Q.empty()){
    node *top = Q.front();
    Q.pop();
    layer[top->layer].push_back(top->data);  //存放到层内 
    if(top->lchild){
      top->lchild->layer = top->layer+1;
      Q.push(top->lchild);
    }
    if(top->rchild){
      top->rchild->layer = top->layer+1;
      Q.push(top->rchild);
    }
  }
}

void fuck_layer(){
  for(int i = 0; i < maxn; i++) //隔一层一反转
    if(i % 2 == 0) reverse(layer[i].begin(), layer[i].end());
} 

int main(){
  int cnt;
  cin >> cnt;
  for(int i = 0; i < cnt; i++) cin >> in[i];
  for(int i = 0; i < cnt; i++) cin >> post[i];
  node* T = Create(0, cnt-1, 0, cnt-1); //建树
  BFS(T); //层序遍历
  fuck_layer(); //层序转ZigZagging
  for(int i = 0; i < maxn; i++){  //打印每一层
    for(int j = 0; j < layer[i].size(); j++){
      if(i) cout << ' ';
      cout << layer[i][j];
    }
  }
  return 0;
}

斐斐のBlog