Show problems as
Classic problem #652MediumHash TableTreeDepth-First SearchBinary Tree

Find Duplicate Subtrees

Real-world version: Sections of a Rig That Have a Look-Alike
Tracked in this browser only
Read Find Duplicate Subtrees on LeetCode(opens in a new tab)

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

A cargo rig is given as the flat list rig. It hangs from a single top joint, every joint carries at most two joints below it in a first and a second slot, and either slot may be empty.

A flat list is read level by level: its first entry is the top joint's load, 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. A list that ends early leaves the remaining slots empty. The position of a joint is where its load sits in the list.

A section of the rig is one joint together with everything hanging below it. Two sections are alike when they have the same shape and matching joints carry the same load.

Return the positions of the top joints of the sections that have a look-alike somewhere in the rig. Where several sections are alike, report only the earliest of their positions. List the positions in increasing order.

Examples

Example 1

Input
rig = [5, 4, 6, 7, null, 4, 7, null, null, 7]
Output
[1, 3]

Three joints loaded 7 hang with nothing below them, so all three of those sections are alike and the earliest sits at position 3. Higher up, the joint at position 1 and the joint at position 5 are both loaded 4 and both carry a single 7 in their first slot, so those two sections are alike as well and the earlier of them is at position 1.

Example 2

Input
rig = [1, 2, 2, 5, null, null, 5]
Output
[3]

The two joints loaded 5 hang bare and are alike, so position 3 is reported. The two joints loaded 2 are not alike, because one carries its 5 in the first slot and the other in the second, which is a different shape.

Example 3

Input
rig = [1, 4, 7, 9, 11]
Output
[]

Every load in the rig is different, so no two sections can match.

Constraints

  • The rig holds between 1 and 5000 joints.
  • 1 <= rig.length <= 15000
  • -200 <= rig[i] <= 200
  • 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 find_duplicate_subtrees(rig: list) -> list[int]:
Java
public int[] findDuplicateSubtrees(Integer[] rig)

More on the same topics