Binary Tree Maximum Path Sum

A **path** in a binary tree is a sequence of nodes where each pair of adjacent nodes has an edge. A node can only appear once in the path, and the path does not need to pass through the root.

Given the root of a binary tree, return the **maximum path sum** (the path can start and end at any node).

Examples

Input: root = [1,2,3]

Output: 6

Path: 2 → 1 → 3, sum = 6.

Input: root = [-3]

Output: -3

Only the root node.

Input: root = [-10,9,20,null,null,15,7]

Output: 42

Path: 15 → 20 → 7, sum = 42.

Constraints

• Number of nodes in [1, 3 * 10^4]
• -1000 <= Node.val <= 1000

Complexity Analysis

Time

O(n)

Space

O(h)

Test Cases

#1 Simple three-node tree

Input: [1,2,3]

Expected: 6

#2 Classic LeetCode example

Input: [-10,9,20,null,null,15,7]

Expected: 42

#3 Single negative node

Input: [-3]

Expected: -3

#4 Positive root with negative child

Input: [2,-1]

Expected: 2