PAT 1138

题目 ： Postorder Traversal

分值 ： 25
难度 ： 颠覆题
思路 ： 一开始信心很足，因为中序前序转后序我势在必得，有自己的下标法,然而在这题遇到了坑
       被卡时间了,原因在于下标法依赖于中序的下标作为判断准则,然后建树再遍历,这是会超时
       的,如果单纯的让你去打印后序，直接递归更现实。
坑点 ： 下标法会超时

具体代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>
#include <vector>
using namespace std;
vector <int > pre,in ;
bool FLAG = true ;
void postorder(int prel , int s , int d )
{
    if(s > d) return ;
    int i = s ;
    while(in[i]!=pre[prel]) i++ ;
    postorder(prel+1 ,s , i-1);
    postorder(prel+1+i-s , i+1 ,d);
    if(FLAG)
    {
        cout << in[i]<<endl ;
        FLAG =false ;
    }
}
int main() {
    int N ;
    cin >> N ;
    pre.resize(N) ;
    in.resize(N) ;
    for(int i = 0 ; i < N ;i++)
        cin >>pre[i] ;
    for(int i = 0 ; i < N ;i++)
        cin >>in[i] ;
    postorder(0,0,N-1 );
}