PAT A1020 Tree Traversals
题目
简单来说就是 知后序遍历和中序遍历求层次遍历
思路
- 先根据后序遍历和中序遍历建出二叉树
- BFS求层次遍历
code
# include <cstdio>
# include <queue>
# include <algorithm>
# include <cstring>
using namespace std;
struct node{
int data;
node* lchild;
node* rchild;
};
int in[1999];
int post[1999];
int n;
node* Create(int inL,int inR,int postL,int postR){//建二叉树
if(postL>postR){// 递归临界条件
return NULL;
}
node* root=new node;
root->data=post[postR];
int k;
for(k=inL;k<=inR;k++){
if(in[k]==post[postR])
break;
}
int numleft=k-inL;
root->lchild=Create(inL,k-1,postL,postL+numleft-1);
root->rchild=Create(k+1,inR,postL+numleft,postR-1);
return root;
}
int num=0;//已输出的结点个数
void BFS(node* root){
queue <node*> q;
q.push(root);
while(!q.empty()){
node* now=q.front();
q.pop();
printf("%d",now->data);
num++;
if(num<n) printf(" ");
if(now->lchild!=NULL)
q.push(now->lchild);
if(now->rchild!=NULL)
q.push(now->rchild);
}
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&post[i]);
}
for(int i=1;i<=n;i++){
scanf("%d",&in[i]);
}
int inL,postL;
int inR,postR;
inL=postL=1;
inR=postR=n;
node* root=Create(1,n,1,n);
BFS(root);
return 0;
}