fork 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. ll width(TreeNode* root){
  15.   if(!root)return 0;
  16.  
  17.   queue<pair<TreeNode*,ll>>q;
  18.  
  19.   ll ans = 0;
  20.   q.push({root,0});
  21.  
  22.   while(!q.empty()){
  23.   	auto sz = q.size();
  24.   	ll mmin = q.front().second;
  25.   	ll first = 0; ll last =0;
  26.   	for(int i = 0 ; i < sz;i++){
  27.   		auto u =q.front().first;
  28.   		auto d= q.front().second;
  29.   		q.pop();
  30.   		ll curr = d - mmin;
  31.   		if(i == 0)first = curr;
  32.   		if(i == sz-1)last = curr;
  33.  
  34.   		if(u->left)q.push({u->left,2*curr+1});
  35.   		if(u->right)q.push({u->right,2*curr+2});
  36.  
  37.  
  38.   	}
  39.   	ans = max(ans,last-first+1);
  40.   }
  41.   return ans;
  42. }
  43. TreeNode* buildTree(){
  44. 	int x; cin>>x;
  45. 	if(x == -1)return nullptr;;
  46.  
  47. 	TreeNode* root = new TreeNode(x);
  48. 	queue<TreeNode*>q;
  49. 	q.push(root);
  50.  
  51. 	while(!q.empty()){
  52. 		auto u = q.front();
  53. 		q.pop();
  54.  
  55. 		if(cin>>x && x!=-1){
  56. 			u->left = new TreeNode(x);
  57. 			q.push(u->left);
  58. 		}
  59.  
  60. 			if(cin>>x && x!=-1){
  61. 			u->right = new TreeNode(x);
  62. 			q.push(u->right);
  63. 		}
  64. 	}
  65. 	return root;
  66. }
  67. int main() {
  68. TreeNode* root = buildTree();
  69. cout<<width(root);
  70. 	return 0;
  71. }
Success #stdin #stdout 0s 5304KB
comments (?)
stdin
copy 
1 3 2 5 -1 -1 9 6 -1 7
stdout
copy 
7
https://ideone.com/YQm9vo
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!