PAT (Advanced Level) 1086. Tree Traversals Again (25)

入栈顺序为先序遍历，出栈顺序为中序遍历。

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<stack>

using namespace std;

const int maxn=+;

const int INF=0x7FFFFFFF;

int n,tot;

int Preorder[maxn],Inorder[maxn],Postorder[maxn];

int APreorder[maxn],AInorder[maxn];

int ans[maxn];

struct Binary_Tree

{

    int left;

    int right;

    int date;

} node[maxn];

int p1,p2;

stack<int>s;

void Build_Binary_Tree(int L,int R,int father)

{

    int i,MIN=INF,MAX=-INF;

    for(i=L; i<=R; i++)

    {

        if(APreorder[Inorder[i]]>MAX) MAX=APreorder[Inorder[i]];

        if(APreorder[Inorder[i]]<MIN) MIN=APreorder[Inorder[i]];

    }

    node[tot].date=Preorder[MIN];

    if(father<) node[-father].right=tot;

    if(father>) node[father].left=tot;

    int now=tot;

    tot++;

    if(AInorder[Preorder[MIN]]--L>=)

        Build_Binary_Tree(L,AInorder[Preorder[MIN]]-,now);

    if(R-(AInorder[Preorder[MIN]]+)>=)

        Build_Binary_Tree(AInorder[Preorder[MIN]]+,R,-now);

}

void dfs(int p)

{

    if(node[p].left!=-) dfs(node[p].left);

    if(node[p].right!=-) dfs(node[p].right);

    ans[tot]=node[p].date;

    tot++;

}

int main()

{

    while(~scanf("%d",&n))

    {

        int i;

        tot=;

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

        {

            node[i].left=-;

            node[i].right=-;

            node[i].date=-;

        }

        p1=p2=;

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

        {

            char op[]; scanf("%s",op);

            if(op[]=='u')

            {

                int num; scanf("%d",&num);

                s.push(num);

                Preorder[p1++]=num;

            }

            else if(op[]=='o')

            {

                int top=s.top(); s.pop();

                Inorder[p2++]=top;

            }

        }

        for(i=; i<=n; i++)  APreorder[Preorder[i]]=i;

        for(i=; i<=n; i++ )AInorder[Inorder[i]]=i;

        Build_Binary_Tree(,n,);

        tot=;

        dfs();

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

        {

            if(i<n-) printf("%d ",ans[i]);

            else printf("%d\n",ans[i]);

        }

    }

    return ;

}