← К задачам Деревья: 0/15 решено
Собеседование ← Предыдущая Следующая →

5815. Поддерево другого дерева

Medium 0 решили
Два двоичных дерева заданы списками в порядке уровней: у узла с индексом i левый ребёнок — 2·i+1, правый — 2·i+2. Значение -1 означает, что узла нет. Корень — индекс 0. Если в слоте -1, его потомки в дерево не входят.

sub является поддеревом tree, если в tree есть узел, от которого вниз растёт дерево с теми же значениями и той же формой, что и sub целиком. Лишний ребёнок в этом месте — уже не совпадение.

Пустой sub (пустой список или корень -1) считается поддеревом любого tree. Непустой sub при пустом tree даёт false.

Примеры:

Вход: tree = [3, 4, 5, 1, 2], sub = [4, 1, 2]
Выход: true
Объяснение: От узла 4 вниз те же дети 1 и 2, и дальше пусто — как в sub.
Вход: tree = [3, 4, 5, 1, 2, -1, -1, -1, -1, 0], sub = [4, 1, 2]
Выход: false
Объяснение: У двойки в tree есть левый ребёнок 0. В sub двойка — лист, формы разные.
Вход: tree = [1, 2, 3], sub = [2]
Выход: true
Объяснение: Корень не совпал: у него есть дети. Совпал лист 2.

Ограничения:

0 <= tree.length, sub.length <= 10^4 значение узла от -10^9 до 10^9 и не равно -1 -1 означает отсутствие узла

Теги:

Часто на собесе Деревья

Комментарии (0)

Зарегистрируйтесь или войдите, чтобы оставить комментарий

Пока нет комментариев. Будьте первым!