Maximum Path Sum in a Binary Tree

Given a binary tree represented as a space-separated level order traversal string, compute the maximum path sum. A path is any sequence of nodes connected by parent-child links. The path must contain at least one node and does not need to pass through the root.

Formally, for a path containing nodes with values \(v_1, v_2, \ldots, v_k\), the path sum is given by \(\sum_{i=1}^k v_i\). Your task is to find the maximum possible path sum in the tree.

inputFormat

The input consists of a single line containing a space-separated string that represents a binary tree in level order. The keyword "null" represents a missing node.

outputFormat

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

1 2 3

6