Минимизировать абсолютную разницу между суммой поддеревьев, образованных после разделения двоичного дерева на два

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

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

Пример:

Input:      1
               /  
             2     3
           /        
         4    5     8
                    /  
                  6    7 
Output: 6
Explanation: Split the tree between vertex 3 and 8. Subtrees created have sums 21 and 15

Input:        1
               /    
             2       3
           /       /  
        4     5  6    7
                      
Output: 4
Explanation: Split the tree between vertex 1 and 3. Subtrees created have sums 16 and 12

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

  • Инициализируйте переменную minDiff максимальным значением Integer, в котором будет храниться ответ.
  • Используйте обход в обратном порядке, чтобы сохранить сумму текущего узла, левого поддерева и правого поддерева в текущем узле.
  • Используйте обход в предварительном порядке и при каждом рекурсивном вызове найдите сумму поддеревьев, если разделение происходит между:
    • текущий узел и левый дочерний узел
    • текущий узел и правый дочерний узел
  • Обновлять minDiff , если при любом рекурсивном вызове разница поддеревьев меньше minDiff

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


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

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