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. 	int flag=0;
  55.     queue<pair<node*,int > > q;
  56.     q.push(make_pair(root,0));
  57.     visited[root->data]=1;
  58.     while(!q.empty()){
  59.         pair<node*,int > temp=q.front();
  60.         if(temp.second==level){
  61.         	flag=1;
  62.         	vector<int > v;
  63.         	if(q.empty()){
  64.         		cout<<0<<" ";
  65.         	}
  66.         	else{
  67. 	            while(!q.empty()){
  68. 	            	v.push_back(q.front().first->data);
  69. 	                //cout<<q.front().first->data<<" ";
  70. 	                q.pop();
  71. 	            }
  72. 	            sort(v.begin(),v.end());
  73. 	            for(auto it:v){
  74. 	            	cout<<it<<" ";
  75. 	            }
  76. 	            break;
  77.         	}
  78.         }
  79.         q.pop();
  80.         if(temp.first->left && visited[temp.first->left->data]!=1){
  81.             visited[temp.first->left->data]=1;
  82.             q.push(make_pair(temp.first->left,temp.second+1));
  83.         }
  84.         if(temp.first->right && visited[temp.first->right->data]!=1){
  85.             visited[temp.first->right->data]=1;
  86.             q.push(make_pair(temp.first->right,temp.second+1));
  87.  
  88.         }
  89.         if(parent.find(temp.first)!=parent.end() && visited[parent[temp.first]->data]!=1){
  90.             visited[parent[temp.first]->data]=1;
  91.             q.push(make_pair(parent[temp.first],temp.second+1));
  92.  
  93.         }
  94.     }
  95.     if(flag==0){
  96.     	cout<<0<<" ";
  97.     }
  98. }
  99.  
  100. int main(){
  101. 	int n,x,y,z;
  102. 	cin>>n;
  103. 	int a[n+1];
  104. 	for(int i=0;i<n;i++)
  105. 	{
  106. 		cin>>a[i];
  107. 	}
  108. 	int b[n+1];
  109. 	for(int i=0;i<n;i++)
  110. 	{
  111. 		cin>>b[i];
  112. 	}
  113.     node* root=buildtree(a,b,0,n-1);
  114.     cin>>z;
  115.     while(z--){
  116.         cin>>x>>y;
  117.         preorder(root,x);
  118.        // cout<<target->data<<endl;
  119.         fine(target,y)   ;     //node* temp=find(root,x);
  120. 		cout<<endl;
  121. 		visited.clear();
  122.     }
  123. }
  124.  
Success #stdin #stdout 0s 4508KB
comments (?)
stdin
copy 
4
60 65 50 70
50 65 60 70
2
60 1
65 2
stdout
copy 
65 70 
70
https://ideone.com/vbez9a
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!