Univalue Path Length

mediumSave

Binary TreeDepth-First SearchRecursionTree

Given a binary tree, find the length of the longest path where all nodes along the path have the same value. This path may or may not pass through the root. The path length is defined as the number of nodes in the path.

The value of each node in the tree is given as an integer. You must implement a function maxUnivaluePath(root) where root is the root node of the binary tree.

Example 1

Input

Output

Explanation. In this case, all nodes have the same value, and the entire tree is a univalue path.

Example 2

Input

Output

Explanation. The longest univalue path is to the right-side of the tree with four '5's.

Example 3

Input

Output

Explanation. The longest univalue path is two '5's descending from the right child of the root, including root if considering the matched value.

Example 4

Input

[
  [
    10
  ]
]

Output

Explanation. The tree only has the root node, hence the longest univalue path is length 1.

Follow-up: Could you solve the problem in O(n) time where n is the number of nodes in the binary tree?

Constraints:

1. The binary tree will have between 1 and 10,000 nodes. 2. Node values range from -1000 to 1000.

Views: 3