Maximum Path Sum in a Binary Tree

Given a binary tree, your task is to find the maximum path sum. The path can start and end at any node in the tree. The sum is defined as the sum of the values of the nodes on the path. The input tree is provided as a space‐separated list of values in level order, where the keyword null indicates a missing node.

For example, the input "1 2 3" represents a binary tree with the root node value 1, left child 2, and right child 3. Use an efficient algorithm to handle large trees. Note that the node values may be negative, so a path consisting of a single node might be the maximum.

The solution must read input from stdin and output the answer to stdout.

inputFormat

The input consists of a single line containing the space-separated node values of the binary tree in level order. Use the keyword null for missing nodes. For example:

1 2 3

represents the following binary tree:

    1
   / \
  2   3

outputFormat

Output a single integer representing the maximum path sum found in the binary tree, printed on a single line.

## sample

1

1

</p>