UVA536 二叉树重建 Tree Recovery

根据先序和中序确定后序，建树过程中就可以输出后序。

unordered_map<char,int> pos;
string pre,in;
int n;

char build(int inl,int prel,int len)
{
    if(!len) return ‘^‘;

    int inr=inl+len-1,prer=prel+len-1;
    char root=pre[prel];
    int k=pos[root];

    char lchild=build(inl,prel+1,k-inl);
    char rchild=build(k+1,prel+1+k-inl,len-1-k+inl);
    cout<<root;
    return root;
}

int main()
{
    while(cin>>pre>>in)
    {
        n=in.size();

        for(int i=0;i<n;i++) pos[in[i]]=i;

        build(0,0,n);
        cout<<endl;
    }

    //system("pause");
    return 0;
}

UVA536 二叉树重建 Tree Recovery

原文：https://www.cnblogs.com/fxh0707/p/14323606.html