Maximum Path Sum

A path is a sequence of connected nodes where each pair of neighbours is a parent and its child; it may start and end at any nodes and does not have to pass through the root, but it uses each node at most once. Return the largest sum of the values along any non-empty path.

The tests write a tree as a level-order list (row by row, left to right) with None for a missing child: [3, 9, 20, None, None, 15, 7] is a root 3 with children 9 and 20, where 20 has children 15 and 7.

For [-10, 9, 20, None, None, 15, 7] the answer is 42 (15 + 20 + 7).

Examples

Example 1

Input:

max_path_sum(root)  # root = [-10, 9, 20, None, None, 15, 7]

Output:

42

Example 2

Input:

max_path_sum(root)  # root = [1, 2, 3]

Output:

6

Constraints

• 1 <= number of nodes <= 100000
• The tree is not deeper than 800 levels.
• -1000 <= val <= 1000