本文主要是介绍【PAT】1020 Tree Traversals (25 分),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
struct node
{
int data;
int lchild,rchild;
};
vector<int> post,in;
vector<node> T;
int t_index=0;
int lca(int inl,int inr,int postRoot){
if(inl>inr) return -1;
int inRoot=inl;
while(in[inRoot]!=post[postRoot]) inRoot++;
//T[index]的index可以随意设定,只要与lchild\rchild\以及每次的返回对应
//还是最好设定成index*2+1,index*2+2这种的比较好
T[inRoot].data=post[postRoot];
T[inRoot].lchild=lca(inl,inRoot-1,postRoot-(inr-inRoot)-1);
T[inRoot].rchild=lca(inRoot+1,inr,postRoot-1);
return inRoot;
}
int flag=0;
void levelOrderTraversal(int root){
queue<int> q;
q.push(root);
while(!q.empty()){
int tmp=q.front();
q.pop();
printf("%s%d",flag==1?" ":"",T[tmp].data);
flag=1;
if(T[tmp].lchild!=-1) q.push(T[tmp].lchild);
if(T[tmp].rchild!=-1) q.push(T[tmp].rchild);
}
}
int main(){
int n;
scanf("%d",&n);
post.resize(n+1),in.resize(n+1),T.resize(n+1);
for(int i=1;i<=n;i++) scanf("%d",&post[i]);
for(int i=1;i<=n;i++) scanf("%d",&in[i]);
int root=lca(1,n,n);
levelOrderTraversal(root);
return 0;
}
这篇关于【PAT】1020 Tree Traversals (25 分)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!