03-树3 Tree Traversals Again

题意

给出一个二叉树前序遍历过程中的弹栈和压栈的过程，求这个二叉树的后序遍历。

解题思路

Push过程是前序遍历，Pop过程是中序遍历。
已知前序和中序求后序：
1、确定树的根节点。树根是当前树中所有元素在前序遍历中最先出现的元素。
2、求解树的子树。找出根节点在中序遍历中的位置，根左边的所有元素就是左子树，根右边的所有元素就是右子树。若根节点左边或右边为空，则该方向子树为空；若根节点左边和右边都为空，则根节点已经为叶子节点。
3、递归求解树。将左子树和右子树分别看成一棵二叉树，重复1、2、3步，直到所有的节点完成定位。

参考代码

#include <iostream>
#include <string.h>
#include <stack>
using namespace std;
#define MAXN 40
typedef struct Node{
    int v;
    struct Node *l,*r;
}*tree;
int a[MAXN],b[MAXN];
int n;
int Find(int x){
    for (int i=0;i<n;i++)
        if (b[i]==x)
            return i;
    return -1;
}
void build(tree &t,int k,int l,int r){
    if (l>r) return;
    int mid=Find(a[k]);
    if (mid==-1) return;
    if (t==NULL){
        t=new Node;
        t->v=a[k];
        t->l=t->r=NULL;
    }
    //cout<<k<<" "<<l<<" "<<r<<endl;
    build(t->l,k+1,l,mid-1);
    build(t->r,k+mid-l+1,mid+1,r);
}
int flag=0;
void PostOrder(tree t){
    if (t==NULL) return;
    PostOrder(t->l);
    PostOrder(t->r);
    if (flag==0){
        cout<<t->v;
        flag=1;
    }
    else
        cout<<" "<<t->v;
}
int main(){
    char str[10];
    cin>>n;
    stack<int> s;
    int k=0,k2=0;
    for (int i=0;i<2*n;i++){
        cin>>str;
        if (strcmp(str,"Push")==0){
            cin>>a[k++];
            s.push(a[k-1]);
        }
        else{
            b[k2++]=s.top();
            s.pop();
        }
    }
    tree t=NULL;
    build(t,0,0,n-1);
    PostOrder(t);
    cout<<endl;
    return 0;
}