Show problems as
Classic problem #549MediumTreeDepth-First SearchBinary TreeDP on Trees

Binary Tree Longest Consecutive Sequence II

Real-world version: Longest Stepped Run In The Pipe Tree
Tracked in this browser only
Read Binary Tree Longest Consecutive Sequence II on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A pressure gauge sits at every junction of a binary tree of pipes, and each junction has at most two junctions hanging below it.

The tree is handed to you as a level-order list readings. readings[0] is the root's gauge. Walk the list left to right while keeping a queue of the junctions recorded so far, starting with the root: the next two entries are the lower-left and lower-right slots of the first queued junction, the two after that are the slots of the second queued junction, and so on. An empty slot is written as null, and nothing at all is written for the slots below a null, so a null takes exactly one entry of the list. Once every remaining entry would be null the list may simply stop.

A route is a sequence of one or more distinct junctions in which each junction is joined by a pipe to the next one, going either down to a junction below it or up to the junction above it. A route may therefore climb from one junction up towards the root and then descend into a different branch, and it turns at most once because a tree offers no other way through.

A route is stepped when the gauge changes by exactly one at every step and always in the same direction, so the readings along it either climb by one each time or drop by one each time. Return the number of junctions on the longest stepped route in the tree; a single junction on its own counts as a stepped route of length 1.

Examples

Example 1

Input
readings = [4,5,3,6,null,null,2]
Output
5

The root reads 4, its lower-left junction 5 with a 6 below that, and its lower-right junction 3 with a 2 below that. The route 6, 5, 4, 3, 2 climbs from the 6 up to the root and then descends the other branch, dropping by one at every step, so it is a stepped route through 5 junctions.

Example 2

Input
readings = [5,6,null,5]
Output
2

The root reads 5, its lower-left junction 6, and below that a 5 again. The whole route 5, 6, 5 changes by one at each step but reverses direction in the middle, so it is not stepped; the pair 5, 6 is, giving 2.

Example 3

Input
readings = [3,3,3]
Output
1

Every gauge reads the same, so no step of exactly one exists anywhere and only a single junction on its own qualifies.

Constraints

  • The tree holds k junctions with 1 <= k <= 3 * 10^4.
  • 1 <= readings.length <= 6 * 10^4 + 1
  • -30000 <= readings[i] <= 30000
  • Every entry of `readings` is either a gauge reading or `null`, and `readings[0]` is a reading.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def longest_consecutive(readings: list) -> int:
Java
public int longestConsecutive(Integer[] readings)

More on the same topics