936. Binary Tree Maximum Path Sum (Any to Any)

Given the root of a binary tree, return the maximum path sum of any non-empty path, where a path is any sequence of nodes connected by edges (each node used once) and need not pass through the root. The tree is given as a level-order array with null for missing children.

Input: A level-order array of the tree.

Output: Integer — the maximum path sum.

Examples

Input: [-10,9,20,null,null,15,7]
Output: 42
Explanation: Path 15-20-7 sums to 42.

Input: [1,2,3]
Output: 6
Explanation: Path 2-1-3.

Input: [-3]
Output: -3
Explanation: Single negative node.

Constraints

• 1<=nodes<=3*10^4
• -1000<=value<=1000

Asked by