fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using ll = long long;
  5.  
  6. struct TreeNode{
  7. 	int val;
  8. 	TreeNode* left;
  9. 	TreeNode* right;
  10.  
  11. 	TreeNode(int val):val(val),left(nullptr),right(nullptr){};
  12. };
  13.  
  14. void find(vector<int>&ans,TreeNode* root,int k){
  15. 	if(k<0||root == nullptr)return;
  16. 	if(k == 0 )ans.push_back(root->val);
  17. 	find(ans,root->left,k-1);
  18. 	find(ans,root->right,k-1);
  19. }
  20. void dfs(TreeNode* root,TreeNode* tar,vector<int>&ans,int k,bool &found,int &dist){
  21. 	if(root == nullptr)return;
  22.  
  23. 	if(root == tar){
  24. 		found = true;
  25. 		dist = 0;
  26. 		find(ans,root,k);
  27. 		return;
  28. 	}
  29.  
  30. 	dfs(root->left,tar,ans,k,found,dist);
  31.  
  32. 	if(found){
  33. 		dist++;
  34. 		if(dist == k)ans.push_back(root->val);
  35. 		find(ans,root->right,dist-k-1);
  36. 		return;
  37. 	}
  38.  
  39. 	dfs(root->right,tar,ans,k,found,dist);
  40. 		if(found){
  41. 		dist++;
  42. 		if(dist == k)ans.push_back(root->val);
  43. 		find(ans,root->left,dist-k-1);
  44. 		return;
  45. 	}
  46. }
  47. vector<int>distK(TreeNode* root,TreeNode* tar,int k){
  48. 	vector<int>ans;
  49. 	bool found = false;
  50. 	int dist = 0;
  51.  
  52. 	dfs(root,tar,ans,k,found,dist);
  53. 	return ans ;
  54. }
  55.  
  56. TreeNode* buildTree(){
  57. 	int x; cin>>x;
  58. 	if(x == -1)return nullptr;;
  59.  
  60. 	TreeNode* root = new TreeNode(x);
  61. 	queue<TreeNode*>q;
  62. 	q.push(root);
  63.  
  64. 	while(!q.empty()){
  65. 		auto u = q.front();
  66. 		q.pop();
  67.  
  68. 		if(cin>>x && x!=-1){
  69. 			u->left = new TreeNode(x);
  70. 			q.push(u->left);
  71. 		}
  72.  
  73. 			if(cin>>x && x!=-1){
  74. 			u->right = new TreeNode(x);
  75. 			q.push(u->right);
  76. 		}
  77. 	}
  78. 	return root;
  79. }
  80.  
  81. TreeNode* findNode(TreeNode* root,int val){
  82. 	if(!root)return nullptr;
  83. 	if(root->val == val)return root;
  84. 	TreeNode* left = findNode(root->left,val);
  85. 	if(left)return left;
  86. 	return findNode(root->right,val);
  87. }
  88. int main() {
  89. TreeNode* root = buildTree();
  90. int val,k;
  91. cin>>val>>k;
  92. TreeNode* tar = findNode(root,val);
  93. vector<int>ans = distK(root,tar,k);
  94.  
  95. for(int &x : ans){
  96. 	cout<<x;
  97. }
  98. 	return 0;
  99. }
Success #stdin #stdout 0s 5324KB
comments (?)
stdin
copy 
3 5 1 6 2 0 8 -1 -1 7 4
5 2
stdout
copy 
Standard output is empty
https://ideone.com/fMGXhb
language:
C++14 (gcc 8.3)
created:
1 day 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!