PAT_A1138#Postorder Traversal

Source:

Description:

Input Specification:

Output Specification:

Sample Input:

Sample Output:

Keys:

• 二叉树的遍历

Attention:

• 建树的过程实质上也是遍历二叉树的过程

Code:

 /*

 Data: 2019-05-26 20:53:20

 Problem: PAT_A1138#Postorder Traversal

 AC: 16:20

 题目大意：

 假设二叉树中各个结点权值不同且为正；

 给出先序和中序遍历，求后序遍历中的第一个结点

 */

 #include<cstdio>

 const int M=1e5;

 int pre[M],in[M],f=;

 void Travel(int preL, int preR, int inL, int inR)

 {

     if(preL > preR)

         return;

     int k;

     for(k=inL; k<=inR; k++)

         if(in[k]==pre[preL])

             break;

     int numLeft = k-inL;

     Travel(preL+, preL+numLeft, inL,k-);

     Travel(preL+numLeft+, preR, k+,inR);

     if(f){

         printf("%d\n", in[k]);f=;

     }

 }

 int main()

 {

 #ifdef    ONLINE_JUDGE

 #else

     freopen("Test.txt", "r", stdin);

 #endif

     int n;

     scanf("%d", &n);

     for(int i=; i<n; i++)

         scanf("%d", &pre[i]);

     for(int i=; i<n; i++)

         scanf("%d", &in[i]);

     Travel(,n-,,n-);

     return ;

 }