Минимизируйте изменения для преобразования в дерево с корнем 1, четными левыми дочерними элементами и нечетными правыми дочерними элементами

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

Учитывая бинарное дерево, задача состоит в том, чтобы преобразовать это дерево, используя минимальное количество операций увеличения-уменьшения, в дерево, удовлетворяющее следующим условиям:

  • Корневой узел всегда равен 1.
  • Каждый левый дочерний элемент узла четный.
  • Каждый правый потомок узла нечетный.

Возвратите и выведите минимальное количество операций увеличения-уменьшения, необходимых в конце.

Примеры:

Input: 

 

Output: 3
Explanation: 
Since root is already 1, no change is needed at root
Left child of root node is 2, so no change is needed here.
Right child of root node is 2, so change it to 3, making a change of 1.
Left child of node 2 is 5, so change it to 4, making a change of 1.
Left child of node 3 is 6, so no change is needed here.
Right child of node 3 is 8, so change it to 9, making a change of 1.
Hence total changes needed is 3.

 

Input:

 

Output: 0
Explanation: The given tree already satisfies the given conditions.

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

  • If the root node is not 1, we can keep decrementing it by 1 till it becomes 1. So root-1 operations needed here.
  • If the current node is a left child, and it is odd, we can simply make it even by incrementing or decrementing by 1. So 1 operation is needed here.
  • If the current node is a right child, and it is even, we can simply make it odd by incrementing or decrementing by 1. So 1 operation is needed here.

Therefore, simply traverse the given Tree and:

  • Add root-1 operations to the answer if the root is not 1.
  • Add the count of left child which are odd, to the answer
  • Also add the count of right child which are even, to the answer.

Основываясь на приведенной выше идее, мы можем выполнить обход DFS, выполнив следующие шаги:

  • Обход левого и правого дочерних элементов рекурсивно.
    • Проверьте, не является ли левое значение посещенного узла нулевым, а левое дочернее значение узла нечетным
      • Увеличить ответ на 1
    • Проверьте, не является ли правильное значение посещенного узла нулевым, а правильное дочернее значение узла четным
      • Увеличить ответ на 1
  • Снова рекурсивно вызывайте левый и правый узлы, пока не будет пройдено все дерево.
  • Также проверьте, не равен ли root 1.
    • Если верно, добавьте к ответу значение root_value – 1.
  • Верните ответ в конце.

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

Временная сложность: O(V), где V — количество вершин в данном дереве.
Вспомогательное пространство: O(H), размер стека для вызовов функций, где H — высота дерева.

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