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

Given a non-empty binary tree, find the path from the root node to a leaf node that has the maximum sum. Your task is to compute the maximum sum and return the corresponding path. The path should be output as a sequence of node values starting from the root and ending at the leaf.

Formally, let (T) be a binary tree. If a node is a leaf, then the maximum sum path is just the value of that node. Otherwise, if (L) and (R) are the maximum sum paths of the left and right subtrees respectively, then the maximum sum path of the current node is given by: [ \text{max sum} = \text{node.value} + \max(\text{sum}(L), \text{sum}(R)) ] and the corresponding path is formed by concatenating the current node value with the respective child path. It is guaranteed that the tree is non-empty.

Input/Output Format: The input is provided via standard input (stdin) and the output must be printed to standard output (stdout).

inputFormat

Input is given as a single line containing space-separated tokens representing a binary tree in level order. Each token is either an integer or the string 'null', which represents a missing node. For example:

1 2 3

represents a tree with root 1, left child 2, and right child 3.

outputFormat

Output two lines. The first line contains the maximum sum from the root to a leaf. The second line contains the corresponding path from the root to that leaf, with the node values separated by a single space.## sample

1

1
1