Binary Tree Maximum Path Sum

Problem Return the maximum path sum in a binary tree: a path is any node sequence connected by edges, visiting each node at most once — it may start and end anywhere and need not pass through the root. Node values may be negative.

Input / Output

• Input: tree root. Output: max path sum.

Constraints

• Up to 3*10^4 nodes; values in [−1000, 1000]; O(n) single traversal expected.

Example

• [-10,9,20,null,null,15,7] → 42 (15 + 20 + 7); [2,-1] → 2.