Show problems as
Classic problem #1609MediumTreeBreadth-First SearchBinary Tree

Even Odd Tree

Real-world version: Is the Tower Tidy
Tracked in this browser only
Read Even Odd Tree on LeetCode(opens in a new tab)

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

A tower hangs from a single top tile. Every tile holds at most two tiles below it in a first and a second slot, and either slot may be empty. Each tile shows a number.

A flat list is read level by level: its first entry is the top tile's number, and reading left to right, every entry that is not null claims the next two unused positions as its first and second slot in that order, while null marks an empty slot and claims no positions of its own.

Number the rows of tiles from 0 at the top. The tower is tidy when both of the following hold:

  • Every tile on an even-numbered row shows an odd number, and read left to right the row strictly rises.
  • Every tile on an odd-numbered row shows an even number, and read left to right the row strictly falls.

Return true when the tower is tidy.

Examples

Example 1

Input
tower = [1, 4, 2]
Output
true

Row 0 holds the odd number 1. Row 1 holds 4 then 2, both even and falling, so the tower is tidy.

Example 2

Input
tower = [1, 2, 4]
Output
false

Row 1 holds 2 then 4. Both are even, but an odd-numbered row has to fall from left to right.

Example 3

Input
tower = [1, 4, 2, 3, 5, 7, 9]
Output
true

Row 0 holds 1, row 1 holds 4 then 2, and row 2 holds 3, 5, 7 and 9. The even rows rise through odd numbers and the odd row falls through even ones.

Constraints

  • 1 <= tower.length <= 200000
  • The tower holds between 1 and 10^5 tiles.
  • 1 <= tower[i] <= 10^6
  • The first entry of the list is not null.

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 is_even_odd_tree(tower: list) -> bool:
Java
public boolean isEvenOddTree(Integer[] tower)

More on the same topics