AcWing 1576. 再次树遍历
原题链接
简单
作者:
xxxxuu
,
2021-08-17 10:00:44
,
所有人可见
,
阅读 188
#include <iostream>
#include <stack>
using namespace std;
const int N=40;
int l[N],r[N];
void dfs(int u,int root){
if(u==0) return;
dfs(l[u],root);
dfs(r[u],root);
cout<<u;
if(u!=root) cout<<" ";
}
int main(){
int n;
cin>>n;
//root为根结点
//last为上一个进行操作的结点
//type==0表示上一个操作是push,反之为pop
int root,last=0,type;
stack<int> stk;
for(int i=0;i<2*n;i++){
string op;
cin>>op;
if(op=="Push"){
int x;
cin>>x;
if(!last) root=x; //第一次输入
else{
if(type==0) l[last]=x;
else r[last]=x;
}
type=0; //上一个操作为push
last=x;
stk.push(x);
}
else{
type=1; //上一个操作为pop
last=stk.top();
stk.pop();
}
}
dfs(root,root);
return 0;
}