Войти Регистрация
Алгоритмы

175. Поддеревья с одинаковым набором букв

Средняя

Дерево задано списком nodes: nodes[i] = [буква, left, right], буквы строчные латинские, left и right — индексы детей или -1. Корень — узел 0.

Две вершины одинаковые, если множество букв в вершине и всех её потомках совпадает (сколько раз буква встречается — не важно).

Верните группы одинаковых вершин размером от двух: индексы внутри группы по возрастанию, группы — по первому индексу.

В работе: Дерево рубрикатора, где в узлах теги: одинаковый набор тегов ниже узла — кандидат на склейку разделов.

Пример 1

Ввод
nodes = [["a", 1, 2], ["b", 3, -1], ["a", 4, -1], ["a", -1, -1], ["b", -1, -1]]
Вывод
[[0, 1, 2]]

Поддеревья узлов 0, 1 и 2 содержат {a, b}; узлы 3 и 4 — разные листья.

Пример 2

Ввод
nodes = [["x", -1, -1]]
Вывод
[]

Одна вершина — групп нет.

Ограничения

  • 1 ≤ длина nodes ≤ 10⁵
  • Глубина может достигать 10⁵
  • Лимит — 2 с на тест (2000 мс).
Как вызывается ваш код Читать ввод и печатать ответ не нужно: мы вызываем функцию на каждом тесте и сравниваем то, что она вернула. print() и console.log() уходят в консоль. 
def same_subtrees(nodes):
ДеревьяОбход в глубинуБитовые маскиХеш-таблицацельO(n)

Источник: Яндекс, Weekend Offer, отчёт кандидата на Хабре, 2025. Условие пересказано своими словами.