Maximum Path Sum in Binary Tree

You are given a binary tree represented in level-order (BFS) traversal. Some nodes may be missing (represented by None in the input).

Your task is to compute the maximum path sum. A path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

More formally, if a node has value \(v\) and the maximum contributions from its left and right subtrees are \(L\) and \(R\) respectively (ignoring negative contributions by taking \(\max(0, \cdot)\)), then the maximum path sum for any path passing through that node is given by:

\(v + L + R\)

Your goal is to find the maximum such sum among all possible paths in the tree.

inputFormat

The input is read from standard input with the following format:

• The first line contains an integer \(n\) indicating the number of nodes in the binary tree.
• The second line contains \(n\) tokens separated by spaces. Each token is either an integer or the string None representing a missing node. These tokens represent the values of the nodes in level-order (BFS) traversal.

outputFormat

Output a single integer — the maximum path sum computed for the given binary tree. The answer is printed on standard output.

5
1 -2 3 None -1

4