← Все треки

Секция

Деревья на доске

Рекурсия по узлу, дерево поиска и ответы со всего дерева. На доске и в массиве по уровням приём один и тот же.

Код можно запускать, разбор открыт. Внутри шага задачи усложняются, следующий шаг уже про другую формулировку.

Создайте аккаунт, чтобы видеть прогресс по треку.

Шаг 1. Рекурсия по узлу

Глубина, равенство двух деревьев, баланс и зеркало. После этих четырёх обход уже пишется без долгого разогрева.

  1. — 5602. Глубина двоичного дерева Easy 1490 ₽ 2 решили
  2. — 5603. Одинаковые деревья Easy 1490 ₽ 1 решил
  3. — 5818. Сбалансировано ли дерево Easy 1490 ₽ 0 решили
  4. — 5605. Зеркало дерева Medium 1490 ₽ 0 решили

Шаг 2. Уровни и дерево поиска

Вид справа и путь с суммой, затем проверка, что одно дерево лежит внутри другого. Дальше проверка BST и k-й элемент: вторая задача идёт по порядку inorder.

  1. — 5816. Вид дерева справа Medium 1490 ₽ 0 решили
  2. — 5604. Есть ли путь с суммой Medium 1490 ₽ 0 решили
  3. — 5815. Поддерево другого дерева Medium 1490 ₽ 0 решили
  4. — 5810. Проверка дерева поиска Medium 1490 ₽ 0 решили
  5. — 5817. k-й элемент дерева поиска Medium 1490 ₽ 0 решили

Шаг 3. Ответ со всего дерева

Общий предок, диаметр и максимальная сумма пути возвращают из рекурсии пару значений. Сборка дерева по обходам — задача на конец секции.

  1. — 5606. Ближайший общий предок Medium 1490 ₽ 0 решили
  2. — 5609. Диаметр дерева Hard 1490 ₽ 0 решили
  3. — 5608. Максимальная сумма пути в дереве Hard 1490 ₽ 0 решили
  4. — 5610. Дерево по обходам Hard 1490 ₽ 0 решили