Maximum Path Sum in a Binary Tree

Given a binary tree, 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, let each node have a value (a_i). A path can be represented as a sequence of nodes (n_1, n_2, \ldots, n_k) (with (k \ge 1)) such that each adjacent pair (n_i, n_{i+1}) is connected by an edge. The sum of such a path is (\sum_{i=1}^{k} a_{n_i}). Your goal is to find the maximum possible sum over all paths in the tree.

Note: The tree is provided in level-order format using a JSON array with the keyword null indicating missing nodes.

inputFormat

The input is given as a single line containing a JSON array representing the level order traversal of the binary tree. For example:

[1,2,3,null,null,4,-1]

Here, the first element is the root. 'null' represents a missing child node. It is guaranteed that the input array represents a valid binary tree.

outputFormat

Output a single integer representing the maximum path sum computed for the tree.## sample

[1,2,3,null,null,4,-1]

10