fork download
copy 
  1. #include <iostream>
  2. using namespace std;
  3. #include<string>
  4. struct node
  5. {
  6.     int data;                 
  7.     struct node * left;          
  8.     struct node * right;         
  9. };
  10. void createnode(struct node* root, int p, int c, char dir)
  11. {
  12. 	struct node * temp=(node * )malloc(sizeof(node));
  13.     temp->data=c;
  14.     temp->left=temp->right=NULL;
  15.     if(root->data==p)
  16.     {
  17.     	if(dir=='L')
  18.     		root->left=temp;
  19.     	else if(dir=='R')
  20.     		root->right=temp;
  21.     }
  22.     else
  23.     {
  24.     	if(root->left!=NULL)
  25.     		createnode(root->left,p,c,dir);
  26.     	if(root->right!=NULL)
  27.     		createnode(root->right,p,c,dir);
  28.     }		
  29. }
  30. int findpath(struct node* root, string& path, int num)
  31. {
  32. 	if(root->data==num)
  33. 		return 1;
  34. 	else if((root->left!=NULL)&&(findpath(root->left,path,num)==1))
  35. 	{
  36. 		path+="L";
  37. 		return 1;
  38. 	}
  39. 	else if((root->right!=NULL)&&(findpath(root->right,path,num)==1))
  40. 	{
  41. 		path+="R";
  42. 		return 1;
  43. 	}
  44. 	else 
  45. 		return 0;
  46. }
  47. int findimage(struct node* root,string path)
  48. {
  49. 	for(int i=path.length()-1;i>=0;i--)
  50. 	{
  51. 		if((path[i]=='R')&&(root->left!=NULL))
  52. 			root=root->left;
  53. 		else if((path[i]=='L')&&(root->right!=NULL))	
  54. 			root=root->right;
  55. 		else
  56. 			return -1;
  57. 	}
  58. 	return root->data;
  59. }	
  60. int main() 
  61. {
  62. 	struct node * root;
  63.     root=(node * )malloc(sizeof(node));
  64.     root->left=root->right=NULL;
  65.     root->data=1;
  66.     int n,q;
  67.     cin>>n>>q;
  68.     n--;
  69.     int p,c;
  70.     char dir;
  71.     while(n--)
  72.     {
  73.     	cin>>p>>c>>dir;
  74.     	createnode(root,p,c,dir);
  75.     }
  76.     int num;
  77.     while(q--)
  78.     {
  79.     	cin>>num;
  80.     	string path;
  81.     	findpath(root,path,num);
  82.     	int x=findimage(root,path);
  83.     	cout<<x<<endl;
  84.     }
  85. 	return 0;
  86. }
Success #stdin #stdout 0s 4364KB
comments (?)
stdin
copy 
10 8
1 2 R
1 3 L
2 4 R
2 5 L
3 6 R
3 7 L
5 8 R
5 9 L
7 10 R
2
5
3
6
1
10
9
4
stdout
copy 
3
6
2
5
1
-1
-1
7
https://ideone.com/NcYkmW
language:
C++14 (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!