PAT A1086 Tree Traversals Again
题目
思路
push 为先序遍历
根据题目第一句话 pop为中序遍历
即知道先序遍历和中序遍历来求得后序遍历的顺序
- 根据先+中= 构建树
- 根据树后序遍历
- 在主函数中针对不同的字符串输入需要利用栈分别存在2个数组里。
code
# include <cstdio>
# include <queue>
# include <stack>
# include <algorithm>
# include <cstring>
const int maxn=50;
using namespace std;
struct node{
int data;
node* lchild;
node* rchild;
};
int pre[maxn],in[maxn],post[maxn];
int n;// 结点个数
node* create(int preL,int preR,int inL,int inR){
if (preL>preR) {
return NULL;
}
node* root=new node;
root->data=pre[preL];
int k;
for(k=inL;k<=inR;k++){// k=inL
if (in[k]==pre[preL]) {
break;
}
}
int numleft=k-inL;
root->lchild=create(preL+1, preL+numleft, inL, k-1);
root->rchild=create(preL+numleft+1, preR, k+1, inR);
return root;
}
int num=0;//全局的初始化 而不是在 函数中
void postorder(node* root){
if(root==NULL){
return;
}
//错误❎root->lchild=postorder(root);
// root->rchild=postorder(root);
postorder(root->lchild);
postorder(root->rchild);
printf("%d",root->data);
num++;
if(num<n) printf(" ");
}
int main(){
char str[6];
int x,preIndex=0,inIndex=0;
stack<int> st;
scanf("%d",&n);
for(int i=0;i<2*n;i++){
scanf("%s",str);
if(strcmp(str, "Push")==0){
scanf("%d",&x);
pre[preIndex++]=x;
st.push(x);
}else{
in[inIndex++]=st.top();
st.pop();
}
}
node* root=create(0, n-1, 0, n-1);//node* root
postorder(root);
return 0;
}