Maximum Path Sum in a Binary Tree

You are given a binary tree defined by its level-order traversal. Each node contains an integer value. Missing nodes are denoted by the string null.

The 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.

Your task is to compute the maximum path sum. In other words, let \(S\) be the sum of the values along a path. You need to calculate \[ \max S \] where the maximum is taken over all possible paths in the tree.

Note: The path sum can potentially be negative.

Example:

Input: 1 2 3
Output: 6

Explanation: The tree is as follows:

    1
   / \
  2   3

The optimal path is 2 → 1 → 3, with a total sum of 6.

inputFormat

The input consists of a single line that provides the level-order traversal of the binary tree. Node values are separated by spaces. The string null is used to denote a missing node. For instance:

• A single node tree with value 1 is represented as: 1
• A tree with a root 1 and a left child -2 is represented as: 1 -2 null

outputFormat

Output a single integer representing the maximum path sum of the binary tree.

## sample

1

1

</p>