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

Count Univalue Subtrees

Real-world version: Pods Whose Cluster Reads the Same
Tracked in this browser only
Read Count Univalue Subtrees on LeetCode(opens in a new tab)

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

A cluster hangs from a single top pod. Every pod holds at most two pods below it in a first and a second slot, and either slot may be empty. Each pod shows a reading.

A flat list is read level by level: its first entry is the top pod's reading, 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. An empty list means there is no cluster at all.

A pod is plain when every pod hanging at or below it shows the same reading as the pod itself. A pod with both slots empty is therefore always plain.

Return how many pods are plain.

Examples

Example 1

Input
cluster = [1, 1, 1, 2, 1, 1, 1]
Output
5

The four pods at the bottom are plain on their own. The pod in the top pod's second slot has both its pods reading 1 like itself, so it is plain too. The pod in the first slot has a 2 hanging under it, which spoils that pod and the top pod with it.

Example 2

Input
cluster = [1, 2]
Output
1

The pod hanging in the first slot is plain on its own. The top pod is not, because the reading below it differs.

Example 3

Input
cluster = [7, 7, 7, 7, 7, 7, 7]
Output
7

Every pod shows the same reading, so every one of the seven is plain.

Constraints

  • 0 <= cluster.length <= 2000
  • The cluster holds between 0 and 1000 pods.
  • -1000 <= cluster[i] <= 1000
  • 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 count_unival_subtrees(cluster: list) -> int:
Java
public int countUnivalSubtrees(Integer[] cluster)

More on the same topics