TreeDFSDynamic Programming
A path in a binary tree is a sequence of connected nodes that does not visit any node twice; it does not have to pass through the root. The path sum is the sum of its node values. Find the maximum path sum over all non-empty paths. Build the tree from the level-order input yourself, then solve the problem.
Input
A single line giving the tree in level order, with the word null for a missing child (for example 3 9 20 null null 15 7).
Output
Print the maximum path sum.
Constraints
1 <= number of nodes <= 60 -1000 <= value <= 1000
Example 1
Input
-10 9 20 null null 15 7
Output
42
The path 15 -> 20 -> 7 sums to 42.
Example 2
Input
1 2 3
Output
6
The path 2 -> 1 -> 3 sums to 6.