Maximum Root-to-Leaf Sum in a Binary Tree

You are given a binary tree, and your task is to calculate the maximum sum of values from the root to any leaf node. A leaf node is defined as a node with no children.

The maximum sum can be mathematically described as follows:
(\text{maxSum}(node) = node.value + \max(\text{maxSum}(node.left),, \text{maxSum}(node.right))) for non-leaf nodes, and for a leaf node, (\text{maxSum}(node) = node.value).

The tree is provided in level order format as input, where each node's value is separated by a space and the placeholder "null" represents a missing node. In the case of an empty tree, output 0.

inputFormat

The input consists of a single line containing space-separated tokens representing a level-order traversal of the binary tree. Use the string "null" to denote a missing (empty) node. For example:

10 5 12 4 11 7 2

outputFormat

Output a single integer which is the maximum sum of values from the root to any leaf of the tree.## sample

10 5 12 4 11 7 2

29