fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. struct TreeNode{
  5. 	int val;
  6. 	TreeNode* left;
  7. 	TreeNode* right;
  8.  
  9. 	TreeNode(int val):val(val),left(nullptr),right(nullptr){};
  10. };
  11. int width(TreeNode* root){
  12. 	if(root==nullptr)return 0;
  13. 	queue<pair<TreeNode*,int>>q;
  14. 	q.push({root,0});
  15. int ans = 0;
  16.  
  17.  
  18. 	while(!q.empty()){
  19. 		int size = q.size();
  20. 		int mmin = q.front().second;
  21. 		int first = -1,last =-1;
  22. 		for(int i = 0 ; i < size;i++){
  23. 			auto node=q.front();
  24. 		q.pop();
  25. 		auto u = node.first;
  26.  
  27. 		int cur_id = node.second - mmin;
  28. 			if(i == 0)first = cur_id;
  29. 			if(i == size-1)last = cur_id;
  30. 			//cout<<"first"<<first<<endl;
  31. 		//	cout<<"last"<<last<<endl;
  32. 			if(u->left)q.push({u->left,2*cur_id+1});
  33. 			if(u->right)q.push({u->right,2*cur_id +2});
  34. 		}
  35. 		ans = max(ans,last-first+1);
  36. 	}
  37. 	return ans;
  38. }
  39. TreeNode* buildTree(){
  40. 	int x;cin>>x;
  41. 	if(x==-1)return nullptr;
  42. 	TreeNode* root = new TreeNode(x);
  43.  
  44. 	queue<TreeNode*>q;
  45. 	q.push(root);
  46.  
  47. 	while(!q.empty()){
  48. 		auto u = q.front();q.pop();
  49. 		if(cin>>x && x != -1){
  50. 			u->left = new TreeNode(x);
  51. 			q.push(u->left);
  52. 		}
  53. 			if(cin>>x && x != -1){
  54. 			u->right = new TreeNode(x);
  55. 			q.push(u->right);
  56. 		}
  57.  
  58. 	}
  59. 	return root;
  60. }
  61. int main() {
  62.     TreeNode* root = buildTree();
  63.     cout<<width(root)<<endl;
  64. 	return 0;
  65. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
1 3 2 5 3 -1 9
stdout
copy 
4
https://ideone.com/Q7oWIM
language:
C++14 (gcc 8.3)
created:
7 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!