fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. struct TreeNode{
  4. 	int val;
  5. 	TreeNode* right;
  6. 	TreeNode* left;
  7. 	TreeNode(int val):left(nullptr),right(nullptr),val(val){};
  8. };
  9.  
  10. void helper(int c ,int r , vector<tuple<int,int,int>>&t,TreeNode* root){
  11. 	if(root == nullptr)return;
  12. 	t.emplace_back(c,r,root->val);
  13. 	helper(c-1,r+1,t,root->left);
  14. 	helper(c+1,r+1,t,root->right);
  15. }
  16. vector<vector<int>>vertical(TreeNode* root){
  17. 	vector<tuple<int,int,int>>t;
  18. 	//c,r,val
  19. 	helper(0,0,t,root);
  20. 	sort(t.begin(),t.end());
  21. 	vector<vector<int>>ans;
  22. 	int prev = INT_MIN;
  23. 	for(auto [c,r,val]:t){
  24. 		vector<int>curr;
  25. 		if(prev != c){
  26. 		  ans.push_back({});
  27. 		  prev = c;
  28. 		}
  29. 		ans.back().push_back(val);
  30. 	}
  31. 	return ans;
  32. }
  33. TreeNode* buildTree(){
  34. 	int x;cin>>x;
  35. 	if(x==-1)return nullptr;
  36. 	TreeNode* root = new TreeNode(x);
  37.  
  38. 	queue<TreeNode*>q;
  39. 	q.push(root);
  40.  
  41. 	while(!q.empty()){
  42. 		auto u = q.front();
  43. 		q.pop();
  44.  
  45. 		if(cin>>x && x!=-1){
  46. 			u->left = new TreeNode(x);
  47. 			q.push(u->left);
  48. 		}
  49.  
  50. 			if(cin>>x && x!=-1){
  51. 			u->right = new TreeNode(x);
  52. 			q.push(u->right);
  53. 		}
  54. 	}
  55. 	return root;
  56. }
  57. int main() {
  58.     TreeNode* root = buildTree();
  59.     vector<vector<int>>ans = vertical(root);
  60.  
  61.     for(auto x : ans){
  62.     	for(auto y : x){
  63.     		cout<<y<<" ";
  64.     	}
  65.     	cout<<endl;
  66.     }
  67. 	return 0;
  68. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
3 9 20 -1 -1 15 7
stdout
copy 
9 
3 15 
20 
7
https://ideone.com/gunHWL
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!