Show problems as
Classic problem #543EasyTreeDepth-First SearchBinary TreeDP on Trees

Diameter of Binary Tree

Real-world version: Widest Gallery Walk
Tracked in this browser only
Read Diameter of Binary Tree on LeetCode(opens in a new tab)

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

Learn the pattern firstValidation & Properties · Binary Trees & BST, animated step by step

A gallery branches outward from its atrium. Every room has at most two doorways leading further out, and each room carries one signed humidity reading.

The floor plan arrives as rooms, which lists the gallery one level at a time, left to right. Position 0 holds the atrium. Each room named in the listing claims the next two free positions for its outward doorways, the left doorway first and the right one second. A position holding null means no room hangs there, and it claims no positions of its own. Trailing null positions may be left off the listing.

A walk starts in some room, passes through doorways, and never enters a room twice. Its span is the number of doorways it passes through. The walk may start and end anywhere and does not have to reach the atrium.

Return the largest span any walk in the gallery can reach. A gallery with a lone atrium has a largest span of 0. The humidity readings never affect the answer.

Examples

Example 1

Input
rooms = [12, -3, 40, 7, 6]
Output
3

Walking from the room at position 3 out through position 1, the atrium, and on to position 2 passes through 3 doorways, and nothing longer exists.

Example 2

Input
rooms = [9, 1, null, 5, 7, 8, null, null, -5]
Output
4

The gallery leans to one side. The widest walk runs position 5, position 3, position 1, position 4, position 8 for 4 doorways, and it never enters the atrium; any walk that does turn around at the atrium passes through only 3.

Example 3

Input
rooms = [0]
Output
0

The atrium stands alone, so every walk passes through no doorways at all.

Constraints

  • 1 <= number of listed rooms <= 10^4
  • -100 <= humidity reading <= 100
  • rooms[0] is not null
  • rooms is a valid level-by-level listing: no room hangs below a null position

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 widest_gallery_walk(rooms: list[int | None]) -> int:
Java
public int widestGalleryWalk(Integer[] rooms)

More on the same topics