Java | LeetCode
Задача: 783. Minimum Distance Between BST Nodes
Сложность: easy
Дан корень дерева поиска (BST). Верните минимальную разницу между значениями любых двух различных узлов в дереве.
Пример:
Input: root = [4,2,6,1,3]
Output: 1
👨💻 Алгоритм:
1⃣Инициализируйте minDistance значением MAX_VALUE; это переменная для хранения минимальной разницы.
2⃣Выполните обход дерева поиска в порядке возрастания (in-order traversal) и сохраните узлы в списке inorderNodes.
3⃣Итеративно проходите по списку inorderNodes, начиная с индекса 1. Для каждого элемента на позиции i найдите разницу с элементом на индексе i - 1 и соответствующим образом обновите переменную minDistance.
Верните minDistance.
😎 Решение:
class Solution {
List<Integer> inorderNodes = new ArrayList<>();
private void inorderTraversal(TreeNode root) {
if (root == null) return;
inorderTraversal(root.left);
inorderNodes.add(root.val);
inorderTraversal(root.right);
}
public int minDiffInBST(TreeNode root) {
inorderTraversal(root);
int minDistance = Integer.MAX_VALUE;
for (int i = 1; i < inorderNodes.size(); i++) {
minDistance = Math.min(minDistance, inorderNodes.get(i) - inorderNodes.get(i - 1));
}
return minDistance;
}
}
Ставь 👍 и забирай 📚 Базу знаний
1 · 452 ·