Минимизируйте сумму значений узлов, заполнив заданное пустое дерево таким образом, чтобы каждый узел был НОД своих дочерних элементов.

Опубликовано: 21 Сентября, 2022

Для данного двоичного дерева, состоящего из N узлов, не имеющих значений в нем, и целого числа X , представляющего значение корневого узла, задача состоит в том, чтобы найти минимальную сумму значений всех узлов данного дерева, чтобы значение каждого узел должен быть значением НОД его дочерних элементов. Кроме того, никакие два брата и сестры не могут иметь одинаковое значение.

Примеры:

Input:

Output: 22
Explanation: The given tree can be filled as shown below:

Input: 

Output: 18
Explanation: The given tree can be filled as shown below:

Подход: чтобы минимизировать сумму, оба дочерних элемента могут иметь значение X и 2*X , где X — значение родителя. Теперь, если у узла есть только один дочерний узел, его значение будет равно его родительскому узлу. Но чтобы решить, какой дочерний элемент должен иметь значение X и 2*X для получения минимальной суммы, будет учитываться глубина каждого поддерева для каждого узла. Дочернему элементу с большей глубиной будет присвоено значение X , чтобы он мог передать его большему количеству своих дочерних элементов, в то время как другой получит значение 2*X . Выполните следующие шаги, чтобы решить эту проблему:

  1. Найдите глубину каждого узла и сохраните ее на карте вместе с адресом узла в качестве ключа.
  2. Теперь выполните обход DFS, начиная с корневого узла , и в каждом вызове присваивайте узлу значение X , если он имеет большую глубину, чем его родственный узел. В противном случае присвойте значение 2*X .
  3. После описанного выше шага найдите сумму значений левого и правого дочерних элементов при возврате и верните общую сумму, т. е. сумму значений левого дочернего элемента, правого дочернего элемента и текущего узла в каждом вызове.
  4. После выполнения вышеуказанных шагов выведите значение, возвращенное вызовом DFS , как минимально возможную сумму.

Ниже приведена реализация вышеуказанного подхода:


Временная сложность: O(N)
Вспомогательное пространство: O(1)

РЕКОМЕНДУЕМЫЕ СТАТЬИ