Объясняем условие «на пальцах»
🌲 Что такое бинарное дерево поиска (BST)?
Представь дерево решений, где у каждого узла есть правило:
📜 Правило BST:
• Все числа в ЛЕВОМ поддереве < текущего узла
• Все числа в ПРАВОМ поддереве > текущего узла
Суть задачи:
Тебе дали число n — это количество уникальных чисел от 1 до n.
Вопрос: Сколько разных по структуре бинарных деревьев поиска можно построить из этих чисел?
⚠️ Важно: Нас интересует только структура дерева, а не какие именно числа в узлах!
Примеры «на пальцах»
Пример 1: n = 1
Единственное число: [1]
Только 1 дерево:
1
Ответ: 1 ✅
Пример 2: n = 2
Пример 3: n = 3
Как думать, как программист?
Ключевая идея: Динамическое программирование
Давай подумаем: что если мы выберем корень дерева?
Для n = 3, числа [1, 2, 3]:
🔹 Если корень = 1:
• Слева: 0 узлов (пусто)
• Справа: 2 узла [2, 3]
• Количество деревьев = dp[0] × dp[2]
🔹 Если корень = 2:
• Слева: 1 узел [1]
• Справа: 1 узел [3]
• Количество деревьев = dp[1] × dp[1]
🔹 Если корень = 3:
• Слева: 2 узла [1, 2]
• Справа: 0 узлов (пусто)
• Количество деревьев = dp[2] × dp[0]
Итого: dp[3] = dp[0]×dp[2] + dp[1]×dp[1] + dp[2]×dp[0]
Формула динамического программирования:
dp[i] = сумма для всех корней j от 1 до i:
dp[j-1] × dp[i-j]
Где:
• dp[j-1] = количество деревьев в левом поддереве
• dp[i-j] = количество деревьев в правом поддереве
Базовые случаи:
Решение на Java (Динамическое программирование)
Заключение
Пример, рассмотренный в статье, можно найти по адресу:
https://github.com/ShkrylAndrei/leetcode/blob/main/src/main/java/info/shkryl/task96_uniqueBinarySearchTrees/Solution.java