Maximum Path Sum in a Binary Tree

Maximum Path Sum in a Binary Tree

Find the maximum sum of any path between two nodes in a binary tree.

Input format

The first line contains level-order tokens, where N denotes a null node. Node values are between −50 and 50.

Output format

Print the maximum sum of any node-to-node path.

Constraints

• Values fit in a 64-bit signed integer
• Trailing whitespace and a trailing newline are ignored by the judge

Read from stdin, write to stdout. Sample cases below show the exact format.

-33 12 -47 N 37 -25 -29 N N -18 0 N 8 42 43 N -22 N N -30 N N N N 14

67

-13 -18 17 9 49 29 N N N -15 41 N N 42 6 N N N N N -21

117