fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. class node{
  4. 	public:
  5. 	int data;
  6. 	node *left;
  7. 	node *right;
  8.  
  9. 	node (int data){
  10. 		this->data=data;
  11. 		left=right=NULL;
  12. 	}
  13. };
  14. int search(int pre,int in[],int l,int r){
  15. 	for(int i=l;i<=r;i++){
  16. 		if(in[i]==pre)
  17. 		return i;
  18. 	}
  19. }
  20.  
  21. node *buildtree(int pre[],int in[],int l,int r){
  22. 	if(l>r)
  23. 	return NULL;
  24.  
  25. 	static int i=0;
  26. 	node *root=new node(pre[i++]);
  27. 	int idx=search(root->data,in,l,r);
  28.  
  29. 	root->left=buildtree(pre,in,l,idx-1);
  30.  
  31. 	root->right=buildtree(pre,in,idx+1,r);
  32.  
  33. return root;
  34.  
  35. }
  36. void printkdown(node *root,int k){
  37. 	if(root==NULL || k<0)
  38. 	return;
  39.  
  40. 	if(k==0){
  41. 		cout<<root->data<<" ";
  42. //		return;
  43. 	}
  44.  else if(k>1)
  45. 	printkdown(root->left,k-1);
  46. 	printkdown(root->right,k-1);
  47.  
  48.  
  49. }
  50. int  printkeynode(node *root,int keynode,int k){
  51. 	if(root==NULL)
  52. 	return -1;
  53.  
  54. 	if(root->data==keynode){
  55. 		printkdown(root,k);
  56. 		return 0;
  57. 	}
  58.  
  59. 	int d1=printkeynode(root->left,keynode,k);
  60.  
  61. 	if(d1!=-1){
  62. 		if(d1+1==k){
  63. 			cout<<root->data;
  64. 		}
  65.       else 
  66.  
  67.       printkdown(root->right,k-d1-2);
  68.  
  69.        return d1+1;
  70. 	}
  71.  
  72. 	int d2=printkeynode(root->right,keynode, k);
  73.  
  74. 	if(d2!=-1){
  75. 		if(d2+1==k){
  76. 			cout<<root->data<<" ";
  77. 		}
  78.       else 
  79.  
  80.       printkdown(root->left,k-d2-2);
  81.  
  82. 	return d2+1;	
  83. 	}
  84.  
  85. return -1;	
  86. }
  87. void preorder(node *root){
  88. 	if(root==NULL)
  89. 	return;
  90.  
  91. 	cout<<root->data;
  92. 	preorder(root->left);
  93. 	preorder(root->right);
  94. }
  95.  
  96.  
  97.  
  98.  
  99. int main(){
  100. int n;
  101. cin>>n;
  102. int pre[n],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.  
  110. node *root=buildtree(pre,in,0,n-1);
  111. int p,keynode,dis;
  112. cin>>p;
  113. while(p--){
  114. cin>>keynode>>dis;	
  115. printkeynode(root,keynode,dis);
  116. cout<<endl;
  117.  
  118. }
  119.  
  120. 	return 0;
  121. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
4
60 65 50 70
50 65 60 70
2
60 1
65 2
stdout
copy 
70 
70
https://ideone.com/a57wvP
4
60 65 50 70
50 65 60 70
language:
C++ (gcc 8.3)
created:
4 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!