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

題意就是要按照給定的中序遍歷和后續遍歷順序輸出樹的蛇形遍歷序列?

我們可以先還原出樹 然后在把樹dfs一遍 推出每層的節點有多少 ?記錄下來 在用一個bfs搞出層序遍歷存到vector里

?然后再根據每層的節點數 ?把vector里響應的元素reverse!

CODE:

#include<bits/stdc++.h> #include<vector> using namespace std; int in[35]; int post[35]; int flo[30]; typedef struct node {int key;node *l,*r;node(int k):key(k),l(NULL),r(NULL){} }NN,*NNN; NNN devide(int l,int r,int pl,int pr) {int i,k=post[pr],left,right;for(i=l;in[i]!=k&&i<=r;i++);//lack ;left = i-l;right = r-i;NNN p = (NNN)malloc(sizeof(NN));p->key=k;p->l=p->r=NULL;if(right!=0)p->r=devide(i+1,r,pr-right,pr-1);if(left!=0)p->l=devide(l,i-1,pl,pr-right-1);return p; }void preorder(NNN p) {if(p){printf("%d ",p->key);preorder(p->l);preorder(p->r);} } int flor; void dfs(NNN rt,int f) {if(rt){flo[f]++;dfs(rt->l,f+1);dfs(rt->r,f+1);flor=max(flor,f);} } vector<int>res; void bfs(NNN rt) {queue<NNN>q;q.push(rt);while(q.size()) {NNN a = q.front();q.pop();int t = a->key;res.push_back(t);if(a->l!=NULL)q.push(a->l);if(a->r!=NULL)q.push(a->r);} } int main() {int n;cin>>n;for(int i=1;i<=n;i++)scanf("%d",&in[i]);for(int i=1;i<=n;i++)scanf("%d",&post[i]);NNN rt;rt=devide(1,n,1,n);dfs(rt,1); bfs(rt);int sum=0;vector<int>::iterator ss;vector<int>::iterator ee;for(int i=1;i<=flor;i++){if(i%2==1){ss=res.begin();for(int j=0;j<sum;j++,ss++);ee=ss; for(int j=0;j<flo[i];j++,ee++);reverse(ss,ee);}sum+=flo[i];}for(int i=0;i<n;i++){cout<<res[i];if(i==n-1)cout<<endl;else cout<<" ";}return 0; }

總結

以上是生活随笔為你收集整理的PAT-1127. ZigZagging on a Tree (30)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。