PAT_A1138#Postorder Traversal
Source:
Description:
Input Specification:
Output Specification:
Sample Input:7 1 2 3 4 5 6 7 2 3 1 5 4 7 6 Sample Output:3 Keys:
Attention:
Code:1 /* 2 Data: 2019-05-26 20:53:20 3 Problem: PAT_A1138#Postorder Traversal 4 AC: 16:20 5 6 题目大意: 7 假设二叉树中各个结点权值不同且为正; 8 给出先序和中序遍历,求后序遍历中的第一个结点 9 */ 10 11 #include<cstdio> 12 const int M=1e5; 13 int pre[M],in[M],f=1; 14 15 void Travel(int preL,int preR,int inL,int inR) 16 { 17 if(preL > preR) 18 return; 19 int k; 20 for(k=inL; k<=inR; k++) 21 if(in[k]==pre[preL]) 22 break; 23 int numLeft = k-inL; 24 Travel(preL+1,preL+numLeft,inL,k-1); 25 Travel(preL+numLeft+1,preR,k+1,inR); 26 if(f){ 27 printf("%dn",in[k]);f=0; 28 } 29 } 30 31 int main() 32 { 33 #ifdef ONLINE_JUDGE 34 #else 35 freopen("Test.txt","r",stdin); 36 #endif 37 38 int n; 39 scanf("%d",&n); 40 for(int i=0; i<n; i++) 41 scanf("%d",&pre[i]); 42 for(int i=0; i<n; i++) 43 scanf("%d",&in[i]); 44 Travel(0,n-1,0,n-1); 45 46 return 0; 47 } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |