PAT (Advanced Level) Practice 1086 Tree Traversals Again-蒲公英云

PAT (Advanced Level) Practice 1086 Tree Traversals Again

根据操作写递归就行了，注意一点，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;
}