A root-to-leaf path starts at the root and ends at a leaf. Among all such paths, return the largest possible sum of the node values along the path. Values may be negative, so the maximum can be negative too.
Input format
One line: the binary tree as a level-order array.
The tree is encoded on ONE line as a space-separated level-order (breadth-first) array. The token null marks a missing child; the children of a null are omitted from the array. An empty tree is written as the single token null.
Output format
A single integer: the maximum sum over all root-to-leaf paths. The tree is guaranteed to be non-empty.
Constraints
- The tree has between 1 and 1000 nodes.
- Each node value is an integer with absolute value at most 1000.