PAT (Advanced Level) Practice 1086 Tree Traversals Again

朴灿烈づ我的快乐病毒、 2023-07-03 07:27 7阅读 0赞

根据操作写递归就行了，注意一点，data不是从1到n顺序来的，所以要自己去获取push后面的数字，不能简单的用计数器++。

#include <iostream>
    #include <string>
    #include <vector>
    #include <stdio.h>
    using namespace std;
    struct node{
        node* lchild;
        node* rchild;
        int data;
    };
    vector<int> v;
    string op[100];
    int index=0,n;
    node* createTree(){
        if(index>=2*n) return NULL;
    
        if(op[index][1]=='u'){//push
            node* root = new node;
            string s = op[index];
            s.erase(0,5);
            int sum=0;
            for(int i=0;i<s.size();i++){
                sum=sum*10 + s[i]-'0';
            }
            root->data=sum;
            index++;
            root->lchild=createTree();
            root->rchild=createTree();
            return root;
        }else{
            index++;
            return NULL;
        }
    }
    void posttravel(node* root){
        if(root!=NULL){
            posttravel(root->lchild);
            posttravel(root->rchild);
            v.push_back(root->data);
        }
    }
    int main()
    {
        cin>>n;
        getchar();
        for(int i=0;i<2*n;i++){
            getline(cin,op[i]);
        }
        node* root = createTree();
        posttravel(root);
        for(int i=0;i<v.size();i++){
            cout<<v[i];
            if(i!=v.size()-1) cout<<" ";
        }
        return 0;
    }

发表评论取消回复

表情：

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

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

相关阅读

相关 PAT (Advanced Level) Practice 1086 Tree Traversals Again

根据操作写递归就行了，注意一点，data不是从1到n顺序来的，所以要自己去获取push后面的数字，不能简单的用计数器++。 include <iostream>

朴灿烈づ我的快乐病毒、/ 2023年07月03日 07:27/ 0 赞/ 8 阅读

相关 PAT (Advanced Level) Practice 1107 Social Clusters

解题方法：并查集。把爱好当成并查集元素。对于每个人当爱好只有一个时，不做任何操作。当爱好大于一个时，两两进行并查集的合并操作。遍历完后，就可找出，每

傷城~/ 2023年07月03日 03:22/ 0 赞/ 22 阅读

相关 PAT (Advanced Level) Practice 1029 Median

输入不要用cin，用scanf，不然会超时。真的要吐血了，没想到是这个点...... 使用cin输入数据时最后一个测试点超时，使用scanf直接89ms过，题限是200ms

今天药忘吃喽~/ 2023年07月02日 05:25/ 0 赞/ 25 阅读

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

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

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

相关【PAT (Advanced Level) Practice】PAT (Advanced Level) Practice

1006 Sign In and Sign Out (25 分) At the beginning of every day, the first person who s

川长思鸟来/ 2022年10月12日 01:40/ 0 赞/ 22 阅读

相关【PAT (Advanced Level) Practice】1008 Elevator (20 分)

include<iostream> include<cstdio> include<cstdlib> include<string> i

傷城~/ 2022年10月12日 01:24/ 0 赞/ 197 阅读

相关【PAT (Advanced Level) Practice】1099 Build A Binary Search Tree (30 分)

深搜+广搜 include <iostream> include <stack> include <queue> include <vecto

我不是女神ヾ/ 2022年10月04日 15:46/ 0 赞/ 30 阅读

相关 1086. Tree Traversals Again (25)

An inorder binary tree traversal can be implemented in a non-recursive way with a stack.

﹏ヽ暗。殇╰゛Y/ 2022年05月29日 21:11/ 0 赞/ 124 阅读

相关 PAT (Advanced Level) Practice（更新中）

Source: > [PAT (Advanced Level) Practice][PAT _Advanced Level_ Practice] Reference:

超、凢脫俗/ 2021年12月20日 06:31/ 0 赞/ 215 阅读

相关 PAT (Advanced Level) Practice 1008 Elevator (Python 3)

The highest building in our city has only one elevator. A request list is made up with N

痛定思痛。/ 2021年12月12日 21:25/ 0 赞/ 203 阅读