Maximum Root-to-Leaf Path Sum in a Binary Tree

You are given a binary tree represented by its level-order traversal. Some elements in the traversal may be null indicating the absence of a node. Your task is to compute the maximum sum from the root to any leaf node.

The binary tree is constructed using the level-order list. For each node, if a child value is null, then that child does not exist. The maximum path sum is defined as the sum of node values along a path from the root down to a leaf such that the sum is maximized.

Note: In all formulas below, use LaTeX-style formatting. For example, the maximum sum is defined as \(\max_{\text{path}}\sum_{n \in \text{path}} n.val\).

inputFormat

The input is read from standard input. The first line contains an integer m representing the number of elements in the level-order traversal of the tree. The second line contains m space-separated tokens. Each token is either an integer representing a node's value or the string null (in lowercase) indicating a missing node.

For example:

7
1 2 3 null 5 null null

outputFormat

Output a single integer, which is the maximum sum from the root to a leaf node, printed to standard output.

For example, the output for the above sample is:

8

## sample

7
1 2 3 null 5 null null

8

</p>