题目描述

已知数的前序以及中序遍历，得到后序遍历

发现每次push的数据就是前序遍历结果
而pop则可以是中序遍历

C++ 代码

#include<bits/stdc++.h>
using namespace std;

vector<int>pre;
vector<int>post;
vector<int>in;

void buildTree(int l,int r,int root)
{
    if(l>r)
    return;

    int k=pre[root];
    for(int i=l;i<=r;++i)
    {
        if(in[i]==k)
        {
            buildTree(l,i-1,root+1);
            buildTree(i+1,r,root+i-l+1);
            post.push_back(k);
        }
    }
}


int main()
{
    int n;
    string op;
    stack<int> s;

    cin>>n;
    while(cin>>op)
    {
        if(op=="Push")
        {
            int a;
            cin>>a;
            pre.push_back(a);
            s.push(a);
        }
        else
        {
            in.push_back(s.top());
            s.pop();
        }
    }
    buildTree(0,n-1,0);
    for(auto t:post)
        cout<<t<<" ";
}