1138 Postorder Traversal （25 分）

問題描述：給定一顆二叉樹的先序和中序，求二叉樹後序周遊的第一個數。

解題思路：根據先序和中序通路左子樹。再右子樹，沒有子樹的頂點即為第一個數。

AC代碼：

/*1138 Postorder Traversal （25 分）
 *有左子樹，先通路左子樹，否則通路右子樹。直到沒有子樹結束
 */
#include<iostream>
#include<vector>
using namespace std;
vector<int>pre,in;
int main()
{
    freopen("test.txt","r",stdin);
    int N,i;
    scanf("%d",&N);
    in.resize(N),pre.resize(N);
    for(i=0;i<N;++i)scanf("%d",&pre[i]);
    for(i=0;i<N;++i)scanf("%d",&in[i]);
    int preL=-1,inL=0,inR=N,cnt;
    while(inL<inR){//無孩子了
        ++preL;
        i=inL,cnt=0;
        while(in[i]!=pre[preL])++i,++cnt;//在中序找到左子樹的分界
        if(cnt){//繼續左子樹
            inR=i;
        }else{//找右子樹
            inL=i+1;
        }
    }
    printf("%d",pre[preL]);
    return 0;
}