fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. struct TreeNode{
  4. 	int val;
  5. 	TreeNode*left;
  6. 	TreeNode*right;
  7. 	TreeNode(int val):left(nullptr),right(nullptr),val(val){};
  8. };
  9.  
  10. int path(TreeNode*root,int&maxi){
  11. 	if(root == nullptr)return 0;
  12. 	int left = max(0,path(root->left,maxi));
  13. 	int right = max(0,path(root->right,maxi));
  14.  
  15. 	maxi = max(maxi,left+right+root->val);
  16. 	return max(left,right)+root->val;
  17. }
  18. int sum(TreeNode* root){
  19. 	int maxi = INT_MIN;
  20. 	path(root,maxi);
  21. 	return maxi;
  22. }
  23. TreeNode* buildTree(){
  24. 	int x;cin>>x;
  25. 	if(x== -1)return nullptr;
  26. 	TreeNode* root = new TreeNode(x);
  27.  
  28. 	queue<TreeNode*>q;
  29. 	q.push(root);
  30.  
  31. 	while(!q.empty()){
  32. 		auto u= q.front();q.pop();
  33. 		if(cin>>x&&x!=-1){
  34. 			u->left= new TreeNode(x);
  35. 			q.push(u->left);
  36. 		}
  37.  
  38. 			if(cin>>x&&x!=-1){
  39. 			u->right= new TreeNode(x);
  40. 			q.push(u->right);
  41. 		}
  42. 	}
  43. 	return root;
  44. }
  45. int main() {
  46.     TreeNode* root = buildTree();
  47.     cout<<sum(root);
  48. 	return 0;
  49. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
-10 9 20 -1 -1 15 7
stdout
copy 
42
https://ideone.com/MTq8Yh
language:
C++14 (gcc 8.3)
created:
2 days 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!