max path sum in binary tree

Правка en1, от acash, 2019-11-25 20:03:08

Given a non-empty binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

  -10
   / \
  9  20
    /  \
   15   7

ans = 42

I am beginner please help me. Below maxpathsum function must return int value i am using long long just to avoid to integer overflow input : [1,2] (1 is parent of two) expected output : 3 actual output : every time garbage value on leetcode but sometimes gives correct output as 3 also I know its data type error i want your help because when i try to run it on visual studio or codeblocks ,i am getting correct output as 3. whats wrong in below code.

long long int solve(TreeNode* root,long long int &res) {
	if (root == NULL)return INT_MIN;
	long long int left = solve(root->left, res);
	long long int right = solve(root->right, res);
	//cout << left + right;
	long long int temp = max(left, max(right, left + right)) + root->val;
	res = max(1LL*res, temp);
	res = max(1LL*res,1LL* root->val);
	return max(left + 1LL * root->val, max(right + 1LL * root->val, 1LL * root->val));
}
//below function must return int value 
// i am using long long just to avoid to integer overflow
int maxPathSum(TreeNode* root) {
	long long int res;
    if(root==NULL)return 0;
    if(root->left==NULL && root->right==NULL)return root->val;
	solve(root, res);
	int ans = (int)res;
    return ans;
}
Теги cpp, leetcode

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский acash 2019-11-25 20:03:52 8
en1 Английский acash 2019-11-25 20:03:08 1628 Initial revision (published)