Best Path Anywhere
You are given the root of a binary tree whose values may be negative.
A path is a chain of nodes in which every node is joined to the next one by a parent and child link, and no node is used twice. A path holds at least one node. It may start and end anywhere, and it does not have to pass through the root.
Return the largest sum of values that a path can have.
Trees appear in the tests in level order, with null for a missing child, like [3,9,20,null,null,15,7]. Each node is a TreeNode with .val, .left and .right; the class is already defined for you.
Example 1
The path 6, -3, 5, 4 climbs from a leaf to the root and goes down the other side: 6 - 3 + 5 + 4 = 12.
Example 2
The only path is the single node.
Example 3
The node 9 alone beats any longer path, because the root would take 2 away.
Constraints
1 <= number of nodes <= 40-1000 <= node.val <= 1000
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.