главная новое лучшее написать

tree


3

Ссылка на задачу — 2467. Most Profitable Path in a Tree.

📌 Описание задачи

Дано неориентированное корневое дерево с n узлами (нумерованными от 0 до n-1).

Нужно найти максимальный чистый доход Алисы при оптимальном выборе пути.

💭 Идея

Вместо раздельного запуска BFS для поиска пути Боба и последующего прохода динамического программирования по узлам дерева, мы решим задачу одним рекурсивным DFS-проходом.

Для каждого узла будем вычислять:

Читать дальше →

ответить
3

Ссылка на задачу — 889. Construct Binary Tree from Preorder and Postorder Traversal.

📌 Описание задачи

Нам даны прямой (preorder) и обратный (postorder) обходы бинарного дерева.
Необходимо восстановить дерево по этим обходам.

Основные свойства обходов:

💡 Идея

Для построения дерева используем рекурсивный подход, основанный на двух ключевых наблюдениях:

🔍 Детали подхода

  1. Используем итераторы Peekable<Iterator> для эффективного прохода по preorder и postorder.
  2. Берем значение из preorder и создаем новый узел.
  3. Рекурсивно создаем левое поддерево, если postorder пока не указывает на текущий корень.

Читать дальше →

ответить
3

Ссылка на задачу — 1028. Recover a Tree From Preorder Traversal.

📝 Описание задачи

Дано строковое представление бинарного дерева, полученное в порядке прямого обхода, где:

Например для следующего дерева, представление будет таким: 1-2--3---4-5--6---7

Необходимо восстановить бинарное дерево по этой строке и вернуть его корень.

💡 Идея

Читать дальше →

ответить
3

Ссылка на задачу – 1261. Find Elements in a Contaminated Binary Tree.

📝 Описание задачи

Дано двоичное дерево, в котором:

Значения всех узлов загрязнены (-1).
Нужно реализовать структуру FindElements, которая:

💡 Идея

Восстанавливать дерево не требуется!
Вместо этого мы вычисляем путь к узлу target, определяя его родителя и положение.

🔍 Детали подхода

  1. Поиск родителя (parent):

Читать дальше →

ответить