Untitled
unknown
plain_text
3 years ago
2.4 kB
1
Indexable
#include <stdio.h> #include <stdlib.h> #include <string.h> typedef struct _Node{ int number; struct _Node *left,*right,*prev; }Node; int in[3005]; int order[3005]; char X[3005]; char Y[3005]; int n,xs,ys; void inorder1(Node* root); void inorder2(int N); void find(int m,int w,Node* cur); int main(void){ int N,M,x,y,m; Node* root; scanf("%d",&N); root=(Node*)malloc(sizeof(Node)*(N+2)); root[1].number=1; root[1].prev=NULL; for(int i=0,j=1;i<=N;i+=2,j++){ scanf("%d %d",&root[i].number,&root[i+1].number); root[i].prev=&root[j]; root[i+1].prev=&root[j]; root[j].left=&root[i]; root[j].right=&root[i+1]; } inorder1(root); inorder2(N); scanf("%d",&M); for(int i=0;i<M;i++){ xs=0; ys=0; scanf("%d %d",&x,&y); find(x,1,root); find(y,0,root); for(int j=0;j<=xs && j<=ys;j++){ if(X[j]==Y[j]){ X[j]='\0'; Y[j]='\0'; } else break; } for(int j=0;j<=xs;j++){ if(X[j]!='\0'){ printf("P"); X[j]='\0'; } else break; } for(int j=0;j<=ys;j++){ if(X[j]!='\0'){ printf("%c",Y[j]); Y[j]='\0'; } else break; } printf("\n"); } return 0; } void inorder1(Node* root){ Node* cur=root; if(root->left!=NULL) inorder1(root->left); n++; in[n]=root->number; if(root->right!=NULL) inorder1(root->right); return; } void inorder2(int N){ for(int i=1;i<=N;i++){ order[in[i]]=i; } } void find(int m,int w,Node* cur){ if(cur==NULL) return; if(w==1){ if(order[m]>order[cur->number]){ X[xs]='R'; find(m,1,cur->right); } else if(order[m]<order[cur->number]){ X[xs]='L'; find(m,1,cur->left); } } else{ if(order[m]>order[cur->number]){ Y[ys]='R'; find(m,0,cur->right); } else if(order[m]<order[cur->number]){ Y[ys]='L'; find(m,0,cur->left); } } }
Editor is loading...