fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. vector<int>v; // save in this vector u need to print in sorted order
  5.  
  6. class node{
  7.     public:
  8.     int data ;
  9.     node*left;
  10.     node*right;
  11.  
  12.     node( int d){
  13.         data = d;
  14.         left = NULL;
  15.         right = NULL;
  16.     }
  17. };
  18. node*builttree(int*pre,int*in,int s, int e){
  19. 	static int i = 0;
  20. 	if(s>e){
  21. 		return NULL;
  22. 	}
  23. 	int idx = -1;
  24. 	node*root = new node(pre[i]);
  25. 	for( int j = s; j<= e; j++){
  26. 		if(pre[i] == in[j]){
  27. 			idx = j;
  28. 			break;
  29. 		}
  30. 	}
  31. 	i++;
  32. 	root->left = builttree(pre,in,s,idx-1);
  33. 	root->right = builttree(pre,in,idx+1,e);
  34.  
  35. 	return root;
  36. }
  37.  
  38. node*targetnode(node*root,int A){
  39. 	if(root==NULL){
  40. 		return NULL;
  41. 	}
  42. 	node*temp;
  43. 	if(root->data == A){
  44. 		return root;
  45. 	}
  46. 	node* ls = targetnode(root->left,A);
  47. 	if( ls == NULL){
  48. 		return targetnode(root->right,A);
  49. 	}
  50. 	return ls;
  51. }
  52.  
  53. void printkthlevel(node*root, int k){
  54. 	if(root == NULL){
  55. 		return;
  56. 	}
  57. 	if( k==1 ){
  58. 		v.push_back(root->data);
  59. 	}
  60. 	printkthlevel(root->left,k-1);
  61. 	printkthlevel(root->right,k-1);
  62. 	return;
  63. }
  64. int printatdistancK(node*root,node*target,int k){
  65.     if(root == NULL){
  66.         return -1;
  67.     }
  68.     //reac the target node
  69.     if(root == target){
  70.         printkthlevel(target,k+1);
  71.         return 0;
  72.     }
  73.     // next step - ancestor
  74.     int DL = printatdistancK(root->left,target,k);
  75.     if(DL!= -1){
  76.         //two cases ancestor or
  77.         if(DL+1 == k){
  78.             v.push_back(root->data);
  79.         }
  80.         else{
  81.             printkthlevel(root->right,k-DL-1);
  82.         }
  83.         return 1+DL;
  84.     }
  85.     int DR = printatdistancK(root->right,target,k);
  86.     if(DR!= -1){
  87.         //two cases ancestor or
  88.         if(DR+1 == k){
  89.             v.push_back(root->data);
  90.         }
  91.         else{
  92.             printkthlevel(root->left,k-DR-1);
  93.         }
  94.         return 1+DR;
  95.     }
  96.     return -1;
  97. }
  98. int main() {
  99. 	int n;
  100. 	cin >>n;
  101. 	int pre[n];
  102. 	int in[n];
  103. 	for( int i = 0; i<n; i++){
  104. 		cin >> pre[i];
  105. 	}
  106. 	for( int i = 0; i<n; i++){
  107. 		cin >>in[i];
  108. 	}
  109. 	int t;
  110. 	cin >> t;
  111. 	node*root = builttree(pre,in,0,n-1);
  112. 	while(t--){
  113. 		int A,k;
  114. 		cin >> A>>k;
  115. 		node*target = targetnode(root,A);
  116. 		printatdistancK(root,target,k);
  117. 		if(v.size()==0){
  118. 			cout<<0;
  119. 		}
  120.         else {
  121.             sort(v.begin(),v.end());
  122.             for(int x : v){
  123.                 cout<<x<<" ";
  124.             }
  125.         }
  126.         cout<<endl;
  127.         v.clear(); // clear vector after each test 
  128. 		//case as it defined globally so that easily accessible to all function and we dont need to pass all the time
  129. 	}
  130. 	return 0;
  131. }
Success #stdin #stdout 0.01s 5464KB
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/ODbvDu
language:
C++14 (clang 8.0)
created:
3 years ago
visibility:
public

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!