2022-12-11 Daily Challenge

Posted on:
Posted modified:
In: DailyChallenge

Today I have done leetcode's December LeetCoding Challenge with cpp.

December LeetCoding Challenge 11

Description

Binary Tree Maximum Path Sum

A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. Note that the path does not need to pass through the root.

The path sum of a path is the sum of the node's values in the path.

Given the root of a binary tree, return the maximum path sum of any non-empty path.

 

Example 1:

Input: root = [1,2,3]
Output: 6
Explanation: The optimal path is 2 -> 1 -> 3 with a path sum of 2 + 1 + 3 = 6.

Example 2:

Input: root = [-10,9,20,null,null,15,7]
Output: 42
Explanation: The optimal path is 15 -> 20 -> 7 with a path sum of 15 + 20 + 7 = 42.

 

Constraints:

  • The number of nodes in the tree is in the range [1, 3 * 104].
  • -1000 <= Node.val <= 1000

Solution

class Solution {
  int answer = INT_MIN;
  int solve(TreeNode* root) {
    if(!root) return 0;
    int maxLeft = solve(root->left);
    int maxRight = solve(root->right);
    int val = root->val;
    if(maxLeft > 0) val += maxLeft;
    if(maxRight > 0) val += maxRight;
    answer = max(answer, val);
    return (maxLeft < 0 && maxRight < 0) ? root->val :
           maxLeft > maxRight ? root->val + maxLeft :
                                root->val + maxRight;
  }
public:
  int maxPathSum(TreeNode* root) {
    solve(root);
    return answer;
  }
};

// Accepted
// 94/94 cases passed (62 ms)
// Your runtime beats 27.91 % of cpp submissions
// Your memory usage beats 35.19 % of cpp submissions (27.7 MB)
Algorithm