Блог пользователя acash

Автор acash, история, 5 лет назад, По-английски

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;
}
  • Проголосовать: нравится
  • -6
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

In the function maxPathSum you haven't initialized the variable res . That's why you are getting garbage value every time .