Сложность: easy
Дано корень бинарного дерева поиска (BST), верните минимальную абсолютную разницу между значениями любых двух разных узлов в дереве.
Пример:
Input: root = [4,2,6,1,3]
Output: 1
👨💻 Алгоритм:
1⃣Обход дерева в порядке возрастания (инфиксный обход):
Создайте список inorderNodes для хранения значений узлов.
Выполните инфиксный обход дерева, добавляя значения узлов в список.
2⃣ Нахождение минимальной разницы:
Создайте переменную minDifference и инициализируйте её бесконечностью.
Пройдите по списку inorderNodes, начиная с индекса 1, и найдите минимальную абсолютную разницу между последовательными элементами.
3⃣ Возврат результата:
Верните minDifference.
😎 Решение:
class Solution {
private var inorderNodes: [Int] = []
func getMinimumDifference(_ root: TreeNode?) -> Int {
inorderTraversal(root)
var minDifference = Int.max
for i in 1..<inorderNodes.count {
minDifference = min(minDifference, inorderNodes[i] - inorderNodes[i - 1])
}
return minDifference
}
private func inorderTraversal(_ node: TreeNode?) {
guard let node = node else { return }
inorderTraversal(node.left)
inorderNodes.append(node.val)
inorderTraversal(node.right)
}
}Ставь 👍 и забирай 📚 Базу знаний