A1086-Tree Traversals Again

几乎和1020一样,还是要弄清楚建树的问题,是个套路问题

#include<bits/stdc++.h>
using namespace std;
struct node
{
    int data;
    node* left;
    node* right;
};
int N;
vector<int> in,pre;
node* create(int preL,int preR,int inL,int inR) //序列区间 
{
    if(preL>preR)
        return NULL;
    node* root=new node;
    root->data=pre[preL];
    int i;
    for(i=inL;i<=inR;i++)
        if(in[i]==pre[preL])
            break;
    int numLeft=i-inL;
    root->left=create(preL+1,preL+numLeft,inL,i-1);
    root->right=create(preL+numLeft+1,preR,i+1,inR);
    return root;
}
int num=0;
void postorder(node* root)
{
    if(root==NULL)
        return;
    postorder(root->left);
    postorder(root->right);
    printf("%d",root->data);
    num++;
    if(num<N)
        printf(" ");

}
int main()
{
    
    scanf("%d",&N);
    string op;
    int num;
    stack<int> st;
    getchar();
    for(int n=0;n<N*2;n++)
    {
        
        getline(cin,op);
        if(op.substr(0,4)=="Push")
        {
            op=op.erase(0,5);
            num=atoi(op.c_str());
            st.push(num);
            pre.push_back(num);
        }
        else
        {
            in.push_back(st.top());
            st.pop();
        }       
    }
    node* root=create(0,N-1,0,N-1);
    postorder(root);
    return 0;
    
}
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 我们是高中同学。 他沉默,我慢热。 报道那天,我埋着头看桌子上摆着的那本《雨季不再来》,什么也没有注意。 新生军训...
    栀疑阅读 229评论 0 0
  • 雨落蛙鸣两处惊, 初抛粉面动香魂。 细匀慢剪羞国色, 移步凌波跨玉盆。
    sc无心草阅读 286评论 0 2
  • “喜欢一个人最明显的表现就是分享废话了 ​” 但是我要说对不起,我不喜欢你。
    三巡酒过你在角落_阅读 151评论 0 0