fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. class node{
  5. 	public:
  6. 			int data;
  7. 			node* left;
  8.             node* right;
  9. 			node(int d){
  10. 				data=d;
  11. 				left=right=NULL;
  12. 			}
  13. };
  14. node* buildtree(int* pre,int* ino,int s,int e){//s & e are indexes of inorder array
  15. 	static int i=0;
  16. 	if(e<s){
  17. 		return NULL;
  18. 	}
  19. 	node* root=new node(pre[i]);
  20. 	int idx=-1;
  21. 	for(int j=s;j<=e;j++){
  22. 		if(ino[j]==pre[i]){
  23. 			idx=j;break;
  24. 		}
  25. 	}
  26. 	i++;
  27. 	root->left=buildtree(pre,ino,s,idx-1);
  28. 	root->right=buildtree(pre,ino,idx+1,e);
  29. 	return root;
  30. }
  31.  
  32. map<int ,int > visited;
  33. map<node*, node* > parent;
  34. node* target=NULL;
  35.  
  36. void preorder(node* root,int x){
  37.     if(root==NULL){
  38.         return;
  39.     }
  40.     cout<<root->data<<" ";
  41.     if(root->data==x){
  42.         target=root;
  43.     }
  44.     if(root->left){                         //making parent map
  45.         parent[root->left]=root;
  46.     }
  47.     if(root->right){
  48.         parent[root->right]=root;
  49.     }
  50.     preorder(root->left,x);
  51.     preorder(root->right,x);
  52. }
  53. void fine(node* root,int level){
  54.     queue<pair<node*,int > > q;
  55.     q.push(make_pair(root,0));
  56.     visited[root->data]=1;
  57.     while(!q.empty()){
  58.         pair<node*,int > temp=q.front();
  59.         if(temp.second==level){
  60.             while(!q.empty()){
  61.                 cout<<q.front().first->data<<endl;
  62.                 q.pop();
  63.             }
  64.             break;
  65.         }
  66.         q.pop();
  67.         if(temp.first->left && visited[temp.first->left->data]!=1){
  68.             visited[temp.first->left->data]=1;
  69.             q.push(make_pair(temp.first->left,temp.second+1));
  70.         }
  71.         if(temp.first->right && visited[temp.first->right->data]!=1){
  72.             visited[temp.first->right->data]=1;
  73.             q.push(make_pair(temp.first->right,temp.second+1));
  74.  
  75.         }
  76.         if(visited[parent[temp.first]->data]!=1){
  77.             visited[parent[temp.first]->data]=1;
  78.             q.push(make_pair(parent[temp.first],temp.second+1));
  79.  
  80.         }
  81.     }
  82. }
  83.  
  84. int main(){
  85. 	int n,x,y,z;
  86. 	cin>>n;
  87. 	int a[n+1];
  88. 	for(int i=0;i<n;i++)
  89. 	{
  90. 		cin>>a[i];
  91. 	}
  92. 	int b[n+1];
  93. 	for(int i=0;i<n;i++)
  94. 	{
  95. 		cin>>b[i];
  96. 	}
  97.     node* root=buildtree(a,b,0,n-1);
  98.     cin>>z;
  99.     while(z--){
  100.         cin>>x>>y;
  101.         preorder(root,x);
  102.         cout<<target->data<<endl;
  103.         fine(target,y)   ;     //node* temp=find(root,x);
  104. 		visited.clear();
  105.     }
  106. }
  107.  
Runtime error #stdin #stdout 0s 4488KB
comments (?)
stdin
copy 
4
60 65 50 70
50 65 60 70
2
60 1
65 2
stdout
copy 
60 65 50 70 60
https://ideone.com/2fez7i
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!