Highest-total path through a binary tree encoded in level order

A binary tree stores an integer at every node, and values may be negative. A path is a sequence of nodes in which each pair of consecutive nodes is joined by a parent-child edge and no node appears more than once. A path contains at least one node, does not have to include the root, and does not have to start or end at a leaf; it may rise out of one subtree through a node and descend into that node's other subtree. The sum of a path is the total of its node values.

Return the largest sum over all non-empty paths in the tree.

Function Signature

def largest_path_total(values: List[Optional[int]]) -> int:

Rules

• The tree is given in level order. values[0] is the root. Reading left to right, each following pair of entries gives the left and then the right child of the next present node in level order; None means that child is absent.
• Absent nodes have no children listed. Trailing None entries may be omitted.
• The tree has at least one node, so values[0] is never None.
• Return a single integer: the maximum path sum.

Constraints

• The number of nodes is between 1 and 3 * 10^4.
• Every node value is between -1000 and 1000.
• The answer fits in a 32-bit signed integer; its absolute value is at most 3 * 10^7.

Examples

Example 1

Input: values = [4, 2, 7]

Output: 13

Explanation: the path 2 → 4 → 7 uses every node.

Example 2

Input: values = [-5, 8, 3, None, None, 10, -2]

Output: 16

Explanation: node -5 has children 8 and 3; node 8 has no children; node 3 has children 10 and -2. The best path is 8 → -5 → 3 → 10.

Example 3

Input: values = [-7, -3, -9]

Output: -3

Explanation: every value is negative, so the best path is the single node -3.