Найдите минимальный диаметр BST, сумма которого равна целевому значению K.
Учитывая бинарное дерево и цель 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)