本文共 2267 字,大约阅读时间需要 7 分钟。
时间限制
400 ms
内存限制
65536 kB
代码长度限制
16000 B
判题程序
Standard
作者
CHEN, Yue
Suppose that all the keys in a binary tree are distinct positive integers. Given the postorder and inorder traversal sequences, you are supposed to output the level order traversal sequence of the corresponding binary tree.
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 postorder sequence and the third line gives the inorder sequence. All the numbers in a line are separated by a space.
Output Specification:
For each test case, print in one line the level order traversal sequence of the corresponding binary tree. 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:
72 3 1 5 7 6 41 2 3 4 5 6 7
Sample Output:
4 1 6 3 5 7 2
#include#include #include #include #include #define inf 0x3f3f3f3fusing namespace std;int s[135], l[135];int ans[135];typedef int element;typedef struct node{ element data; node *lchild, *rchild;}node, *Tree;Tree creat(int sl, int sr, int ll, int lr){ if(sr-sl <0) return NULL; Tree T; T = new node; T->data = s[sr]; int p=ll; while(l[p] != s[sr]) ++p; int t = lr - p; T->lchild = creat(sl, sr-t-1, ll, p-1); T->rchild = creat(sr-t, sr-1, p+1, lr); return T;}void posd(Tree T){ if(T) { printf("%d ", T->data); posd(T->lchild); posd(T->rchild); }}void level(Tree T){ int out = 0; int in = 0; Tree p[150]; p[in++] = T; int j = 0; while(in > out) { if(p[out]) { ans[j++] = p[out]->data; p[in++] = p[out]->lchild; p[in++] = p[out]->rchild; } out++; }}int main(){ int n, m, k; int i, j; cin>>n; Tree L; for(i = 0; i < n; i++) { scanf("%d", &s[i]); } for(i = 0; i < n; i++) { scanf("%d", &l[i]); } L = creat(0,n-1,0,n-1); posd(L); /*level(L); for(i = 0; i < n-1; i++) { printf("%d ",ans[i]); } printf("%d\n", ans[n-1]);*/}
转载地址:http://dhuwb.baihongyu.com/