PAT甲级1138.

目录

A1138

题目

样例

输入:

7
1 2 3 4 5 6 7
2 3 1 5 4 7 6

输出:

3

思路和坑点

　　思路:
　　我们可以根据一棵树的先序和中序唯一确定一棵树，所以我们使用递归的方式来构建树形，但是我们只需要找到第一个后序的结点就可以了，那么我们可以考虑，如果这棵树有左子树则，后序第一个结点一定在左子树中，如果没有左子树但是有右子树，则后序第一个结点一定在右子树中，否则这棵树没有左子树和右子树，根便是后序序列中的第一个元素。由此逻辑，我们可以得到以下递归代码，实现找到第一个后序结点。

AC代码

#include<bits/stdc++.h>
using namespace std; 
bool flag=false;
int ans;                                            //返回后序的第一个元素
vector<int> pre,in;
void postorder(int pl,int pr,int il,int ir);        //先序和中序确定树形
int main(){    
#ifdef ONLINE_JUDGE    
#else    
    freopen("1.txt", "r", stdin);    
#endif    
    int n;
    scanf("%d",&n);
    pre.resize(n);    in.resize(n);                 //初始化先序和中序的序列大小
    for(int i=0;i<n;i++)                            //读入两个序列
        scanf("%d",&pre[i]);
    for(int i=0;i<n;i++)
        scanf("%d",&in[i]);
    postorder(0,n-1,0,n-1,n-1);
    cout<<ans;
    return 0;    
}
void postorder(int pl,int pr,int il,int ir){        //递归确定树形
    if(pl>pr||flag)    return;                      //如果当前序列为空或者已经找到答案，直接返回上一层
    if(pl==pr){                                     //如果只有一个元素，说明没有左右子树，当前值就是答案
        ans=pre[pl];
        flag=true;
        return ;
    }
    int lnum=0,rnum=0,k;                            //找到当前子树根在中序的位置，左右则为子树
    for(k=il;k<=ir;k++){
        if(in[k]==pre[pl])
            break;
    }
    lnum=k-il;rnum=ir-k;                            //计算左右子树个数
    if(lnum) postorder(pl+1,pl+lnum,il,k-1);        //如果有左子树，则后序第一个元素一定在左子树中
    else if(rnum) postorder(pl+lnum+1,pr,k+1,ir);   //如果没有左子树，则后序第一个元素一定在右子树中
}