The diameter of a binary tree is the number of edges on the longest path between any two nodes. This path may or may not pass through the root, and its endpoints can be any two nodes.
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 diameter measured in edges. An empty tree and a single node both have diameter 0.
Constraints
- The tree has between 0 and 1000 nodes.
- Each node value is an integer with absolute value at most 1000.