PAT A1086

清疚 2022-03-07 13:05 154阅读 0赞

![clipboard.png][]  
和刚刚之前的那道题类似，只不过多考察了一个四大遍历输出中的一个；  
自己跟个智障一样检查了一个小时，结果发现少了一个返回指针，真是干他娘的；

#include<iostream>
    #include<stdlib.h>
    #include<stdio.h>
    #include<stack>
    #include<cstring>
    #include<vector>
    using namespace std;
    using std::vector;
    const int maxn=40;
    int n;
    vector<int>pre;
    vector<int>in;
    stack<int>s;
    struct node{
        int data;
        node* lchild;
        node* rchild;
    };
    
    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 lnum=i-inl;
        root->lchild=create(prel+1,prel+lnum,inl,i-1);
        root->rchild=create(prel+lnum+1,prer,i+1,inr);
        return root;
    }
    int num=0;
    void postorder(node* root){
        if(root==NULL)
            return;
        postorder(root->lchild);
        postorder(root->rchild);
        printf("%d",root->data);
        num++;
        if(num<n)
            printf(" ");
    }
    
    int main(){
        scanf("%d",&n);
        char str[5];
        int x;
        for(int i=0;i<2*n;i++){
            scanf("%s",str);
            if(strcmp(str,"Push")==0){
                scanf("%d",&x);
                pre.push_back(x);
                s.push(x);
            }else{
                in.push_back(s.top());
                s.pop();
            }
        }
        node* root=create(0,n-1,0,n-1);
        postorder(root);
        system("pause");
        return 0;
    }

[clipboard.png]: /images/20220307/778ef34033b84339a3377b1de21ba190.png

发表评论取消回复

表情：

评论列表（有 0 条评论，154人围观）

还没有评论，来说两句吧...

相关阅读

相关 PAT~乙级~1086 就不告诉你 ~python

题目描述：做作业的时候，邻座的小盆友问你：“五乘以七等于多少？”你应该不失礼貌地围笑着告诉他：“五十三。”本题就要求你，对任何一对给定的正整数，倒着输出它们的乘积。 ![

冷不防/ 2023年10月11日 11:55/ 0 赞/ 39 阅读

相关【PAT (Advanced Level) Practice】1086 Tree Traversals Again (25 分)

众所周知只有前序遍历和后序遍历是不可能推出中序遍历的，所以我就不废话了由树的前序遍历和中序遍历可以推后序遍历由树的中序遍历和后序遍历可以推前序遍历 incl

短命女/ 2023年01月24日 02:08/ 0 赞/ 7 阅读

相关 PAT乙级1086

1086 就不告诉你（15 分）做作业的时候，邻座的小盆友问你：“五乘以七等于多少？”你应该不失礼貌地围笑着告诉他：“五十三。”本题就要求你，对任何一对给定的正整数，倒着

落日映苍穹つ/ 2022年05月13日 12:26/ 0 赞/ 166 阅读

相关 PAT A1063

![clipboard.png][] 这里面还是用到了set去重，还是要多掌握stl的用法；这里注意一个巧妙地处理；由于我们寻找的时两个集合a,b的不重复元素，

以你之姓@/ 2022年03月07日 14:22/ 0 赞/ 156 阅读

相关 PAT A1104

![clipboard.png][] 如果采用单纯的暴力枚举，会出现超时问题，可以跟绝递推来找出来规律；代码如下： include<iostream>

亦凉/ 2022年03月07日 14:08/ 0 赞/ 170 阅读

相关 PAT A1086

![clipboard.png][] 和刚刚之前的那道题类似，只不过多考察了一个四大遍历输出中的一个；自己跟个智障一样检查了一个小时，结果发现少了一个返回指针，真是干

清疚/ 2022年03月07日 13:05/ 0 赞/ 155 阅读

相关 PAT A1121

![clipboard.png][] 水题，但是通过这一题需要改进一点；对于hash赋初值的时候一定要谨慎一点，不要随便赋值0，视输入的数据而定； inclu

今天药忘吃喽~/ 2022年03月07日 10:44/ 0 赞/ 175 阅读

相关 PAT A1029

![clipboard.png][] 起先自己想尝试性的直接排序找中位数，内存直接超限；其实这道题可以采用归并排序的思路来做：但是示例依旧白给。。。不过还是展现了

﹏ヽ暗。殇╰゛Y/ 2022年03月07日 10:24/ 0 赞/ 198 阅读

相关 PAT A1043

![clipboard.png][] 简单的不用考虑平衡的二叉查询树；我发现我有读题障碍症。。。 include<iostream> include

迷南。/ 2022年03月07日 03:46/ 0 赞/ 179 阅读

相关 PAT A 1025 PAT Ranking

1025 PAT Ranking (25 分) Programming Ability Test (PAT) is

怼烎@/ 2022年02月01日 10:53/ 0 赞/ 187 阅读