A binary tree of relay-station signal strengths is given in level-order form (a single line of space-separated tokens, null marking a missing child; every non-null node contributes exactly two following tokens for its children). The tree always has at least one node.
Define the distance between two nodes as the number of edges on the unique path connecting them (a node's distance to itself is 0). Find the maximum such distance achieved by any pair of nodes in the tree. If several pairs of nodes achieve this maximum distance, consider all paths of that maximum length and print the greatest possible sum of the node values that lie on any one of them.
Line 1: space-separated level-order tokens describing the binary tree (integers and the token null). The tree has at least 1 node.
A single integer: the sum of node values along a maximum-distance path, chosen as described above.
Example 1
Input
1 2 3 4 5
Expected
11
Explanation
The longest path is 4 -> 2 -> 1 -> 3 (3 edges), or the tied 5 -> 2 -> 1 -> 3. The larger of the two sums, 4+2+1+3=10 vs 5+2+1+3=11, is 11.
Example 2
Input
10
Expected
10
Explanation
A single node: the only path has 0 edges and its sum is just 10.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →