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