Binary Tree Maximum Path Sum

hard

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

The path sum is the sum of the node values in the path.

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

Test Cases

Copy an input into the main harness and Run to verify

Input

root = [1,2,3]

Expected Output

6

Explanation: The path 2 -> 1 -> 3 sums to 6.

Input

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

Expected Output

42

Explanation: The path 15 -> 20 -> 7 sums to 42.

Constraints

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

Hints

Hint 1 — click to reveal

Separate two quantities: the best path that *bends* at a node, and the best path you can *extend upward* from it.

Hint 2 — click to reveal

A subtree contributing a negative total should be dropped — clamp it to zero.

Java Compiler