Longest Univalue Path in a Binary Tree

Given a binary tree, find the length of the longest path where all the nodes have the same value. The path length is defined as the number of edges between the nodes. Note that the path does not necessarily need to pass through the root.

For example, consider the following binary tree:

    5
   / \
  4   5
 / \   \
1   1   5

The longest univalue path is the one formed by the two right nodes, so the answer is 2.

The answer may be expressed using the following formula in LaTeX:

$$ ans = \max_{node \in tree} (leftArrow + rightArrow) $$

where leftArrow and rightArrow are the lengths of the paths of same-value nodes extending from the left and right children of a node, respectively.

inputFormat

The input is provided as a single line representing the level-order traversal of the binary tree. The values are separated by spaces. Use the string null to represent a missing (empty) node.

For example:

5 4 5 1 1 null 5

outputFormat

Output a single integer representing the length of the longest path (in terms of number of edges) where every node in the path has the same value.

## sample

5 4 5 1 1 null 5

2