1127. ZigZagging on a Tree (30)

时间限制

400 ms

内存限制

65536 kB

代码长度限制

16000 B

判题程序

Standard

作者

CHEN, Yue

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++;

    }

  }

}

巴特西

pat 甲级 1127. ZigZagging on a Tree (30)

1127. ZigZagging on a Tree (30)

最新文章

热门文章