Practice/Salesforce/Leetcode 124. Binary Tree Maximum Path Sum

Leetcode 124. Binary Tree Maximum Path Sum

CodingMust

Problem

Given the root of a binary tree, determine the maximum sum achievable by any path within the tree.

A path is defined as any sequence of nodes where each node appears at most once, and adjacent nodes in the sequence share a parent-child relationship. The path does not need to pass through the root node, and it can start and end at any nodes in the tree.

Your task is to find the path with the largest sum of node values. Note that node values can be negative, so you'll need to handle cases where including certain nodes might decrease the total sum.

Requirements

1. Return the maximum sum as an integer
2. Handle trees where all values are negative (return the least negative value)
3. Consider paths of any length, including single-node paths
4. Each node can only be used once in a given path
5. The path must be contiguous (following parent-child connections)

Constraints

• The number of nodes in the tree is in the range [1, 30000]
• Node values are in the range [-1000, 1000]
• Time complexity should be O(n) where n is the number of nodes
• Space complexity should be O(h) where h is the height of the tree (for recursion stack)

Examples

Example 1:

Input: root = [1, 2, 3] Output: 6 Explanation: The optimal path is 2 -> 1 -> 3 with a 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 sum of 15 + 20 + 7 = 42

Example 3:

Input: root = [-3] Output: -3 Explanation: A single node tree has only one possible path: the node itself

Example 4:

Input: root = [-2, -1, -5] Output: -1 Explanation: When all values are negative, choose the path with just the least negative node