Longest same-role chain: hints, no solution
Medium · Trees
In a binary reporting tree every node holds a role code. A chain is a path that starts at some employee and repeatedly steps down to one direct report, going only downward, never back up. A same-role chain is a chain in which every employee has the same role code.
The tree is given in level order: the root first, then the children of each present node from left to right, with null standing for a missing child. Nodes below a missing child are not listed.
Return the number of employees in the longest same-role chain. A single employee is a chain of length 1, and an empty tree has length 0. The chain may start anywhere, not only at the top.
Examples
- Input
- tree = [4, 4, 5, 4, 4, null, 5]
- Output
- 3
- Note
- Going 4, 4, 4 down the left side gives three employees with role 4.
- Input
- tree = [1, 2, 3]
- Output
- 1
- Note
- Every parent and child differ in role, so the best chain is one employee.
Constraints
- 0 <= number of employees <= 2000
- Role codes are integers from 0 to 1000
Hint 1: a nudge
If you stand on one employee and only look downward, how long is the best matching chain that begins right here?
Unlock the full hints and timed practice with a pass
The second and third hints and the timed, runner-checked practice are part of a pass.