给定一棵二叉树的后序遍历和中序遍历,请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。
输入格式:
输入第一行给出一个正整数N(≤30),是二叉树中结点的个数。第二行给出其后序遍历序列。第三行给出其中序遍历序列。数字间以空格分隔。
输出格式:
在一行中输出该树的层序遍历的序列。数字间以1个空格分隔,行首尾不得有多余空格。
输入样例
1 2 3
| 7 2 3 1 5 7 6 4 1 2 3 4 5 6 7
|
输出样例
思路
这道题就是经典的根据遍历序列恢复二叉树,采用递归的方式,一步一步来即可。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59
| #include<bits/stdc++.h> using namespace std; const int maxn = 35; typedef struct node { int data; struct node *left; struct node *right; }Node,*Bitree; int n; int post[maxn],in[maxn]; vector<int> res; Bitree Rebitree(int post[],int p,int in[],int q,int n) { if(n <= 0) return NULL; Bitree T = (Bitree)malloc(sizeof(Node)); T->data = post[p + n -1]; int i = q; for(i; i<q + n; i++){ if(in[i] == T->data) break; } if(i == q) T->left = NULL; else T->left = Rebitree(post,p,in,q,i-q); if(i == q + n) T->right = NULL; else T->right = Rebitree(post, i - q + p, in, i + 1, q + n -i -1); return T; } void LayerOrder(Bitree T) { queue<Bitree> q; if(!T) return; q.push(T); while(q.size()) { auto t = q.front(); q.pop(); res.push_back(t->data); if(t->left) q.push(t->left); if(t->right) q.push(t->right); } } void Print() { for(int i=0;i<res.size();i++){ if(i) cout << " "; cout << res[i]; } } int main() { int n; cin >> n; for(int i=0;i<n;i++) cin >> post[i]; for(int i=0;i<n;i++) cin >> in[i]; Bitree T = Rebitree(post,0,in,0,n); LayerOrder(T); Print(); return 0; }
|