534. Same-Value Trail
A telecom network of relay stations is stored as a binary tree root, and each station carries an integer frequency. A trail is a path that starts at any station, ends at any station, moves only along parent-child links, and never visits a station twice. It does not have to pass through the root. A trail is steady when every station on it has the same frequency. Return the length, counted in links (edges) rather than stations, of the longest steady trail. A single station has length 0, and an empty tree also gives 0.
Example 1
- Input:
- root = [2,2,2,2,2,null,7,2]
- Output:
- 4
- Explanation:
Five of the stations carry frequency 2 and a trail through them from the deepest 2 up to the root and down to the right child spans four links; the 7 is excluded.
Example 2
- Input:
- root = [4,6,4,null,null,4,4]
- Output:
- 2
- Explanation:
The bottom three 4s form a trail 4 - 4 - 4 of two links; the 6 breaks any longer one.
Example 3
- Input:
- root = [5,6,7,8]
- Output:
- 0
- Explanation:
All values are different, so no trail has even a single link.
Constraints
0 ≤ number of nodes ≤ 500
-1000 ≤ Node.val ≤ 1000
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n)
- Space
- O(h)