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 ```python 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.