Sum of Longest Root-to-Leaf Path in a Binary Tree

Given a binary tree represented in level order where the null node is denoted by 'N', your task is to compute the sum of all nodes on the longest path from the root to a leaf. In the case that there are multiple paths of the same longest length, choose the path with the maximum sum.

More formally, let (T) be a binary tree. For a root-to-leaf path (P), let (\ell(P)) be its length (number of nodes) and (S(P)) be the sum of the node values on the path. You are to compute (\max { S(P) : P\ is\ a\ root-to-leaf\ path,\ and\ if\ two\ paths\ have\ the\ same\ length,\ choose\ the\ one\ with\ the\ greater\ sum }).

inputFormat

Input is provided as a single line from standard input containing the level order traversal of the binary tree. The node values are separated by spaces and 'N' represents a null node. For example, the input:

1 2 3 N N 4 5

represents a binary tree with root value 1, left child 2, right child 3, and 2 has no children while 3 has left child 4 and right child 5.

outputFormat

Output a single integer to standard output, which is the sum of the nodes on the longest root-to-leaf path. If multiple such paths exist with equal length, output the maximum sum among them.## sample

1 3 2

4