Найдите минимальный диаметр BST, сумма которого равна целевому значению K.

Опубликовано: 27 Февраля, 2023

Учитывая бинарное дерево и цель K , задача состоит в том, чтобы найти диаметр минимального поддерева, сумма которого равна K , которое также является бинарным деревом поиска. Верните -1, если это невозможно.

Примеры:

Input: K = 38
          13
        /    
      5       23
     /      /
 N  17   N   N
     /  
  16   N
Output: 3
Explanation: 5, 17, 16 is the smallest subtree with diameter 3.

Input: K = 73
            7
          /  
       N     23
            /    
         10      23
        /       /
   N   17   N   N
Output: -1
Explanation: No subtree is BST for the given target.

Подход:

This problem can be solved using the idea of Dynamic Programming on Trees. Store the sum and diameter of every subtree and check if a subtree with sum K is also a binary search tree or not.

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

  • Создайте хэш-таблицы для хранения суммы поддерева, диаметра поддерева, минимального значения поддерева и максимального значения поддерева.
  • Инициализируйте ответ как бесконечность.
  • Теперь сохраните все значения в хеш-таблицах и проверьте, является ли данное бинарное дерево BST, используя обход в глубину.
  • При обходе будут заполнены только хеш-таблицы.
  • Чтобы двоичный файл был BST, должны быть выполнены следующие 3 условия:
    • Левое и правое поддеревья должны быть BST.
    • Максимальное значение левого поддерева < значение текущего узла
    • Минимальное значение правого поддерева > значение текущего узла

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

Сложность времени: НА)
Вспомогательное пространство : O(N)

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