PAT甲 1020 Tree Traversals （树的后序中序->层序）
1020 Tree Traversals (25 分)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:7 2 3 1 5 7 6 4 1 2 3 4 5 6 7 Sample Output:
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 using namespace std; 5 int post[35],in[35]; 6 int a[11000]; 7 //root是后序中的当前根的位置，st,ed是该子树在中序遍历中的最左位置和最右位置
8 void dfs(int root,int st,int ed,int index) 9 { 10
11 if(st>ed) 12 return; 13 int i=st; 14 while(in[i]!=post[root]) 15 i++; 16 //cout<<post[root]<<" "; 17 // cout<<"index="<<index<<" "<<"root="<<post[root]<<endl;
18 a[index]=post[root]; 19 dfs(root-(ed-i+1),st,i-1,index*2); 20 dfs(root-1,i+1,ed,index*2+1); 21 } 22 int main() 23 { 24 int n; 25 cin>>n; 26 for(int i=0;i<n;i++) 27 cin>>post[i]; 28 for(int i=0;i<n;i++) 29 cin>>in[i]; 30 dfs(n-1,0,n-1,1); 31 int cnt=0; 32 for(int i=1;i<10000;i++) 33 { 34 if(a[i]!=0) 35 { 36 cnt++; 37 if(cnt==n) 38 { 39 cout<<a[i]; 40 break; 41 } 42 else
43 cout<<a[i]<<" "; 44 } 45 } 46 return 0; 47 }
（编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |