Количество BST с N узлами высотой не менее K

Даны два положительных целых числа N и K , задача состоит в том, чтобы найти количество бинарных деревьев поиска (BST) с N узлами высоты, большей или равной K .

Примечание . Здесь высота относится к максимальной глубине BST.

Примеры :

Input: N = 3, K = 3
Output: 4
Explanation:
There are 4 possible binary search trees with height greater than or equal to K.

1                   1                        3                      3                                     
                                            /                     /
  2                   3                   2                     1
                      |                   /                         
    3               2                  1                          2

Input: N = 4, K = 2
Output: 14

Подход : Эту проблему можно решить с помощью рекурсии. Выполните следующие шаги, чтобы решить проблему:

• Базовый случай: если N равно 1 , верните 1 .
• Инициализируйте переменную countBsts как 0 , чтобы сохранить количество действительных BST.
• Выполните итерацию в диапазоне [1, N], используя переменную i:
  • Если i-1 и Ni больше, чем равно K , то:
    • Рекурсивно вызовите функцию для левого поддерева с узлами i-1 и высотой K-1 , которая найдет количество способов создать левое поддерево .
    • Рекурсивно вызовите функцию для правого поддерева с узлами как N – i и высотой как K – 1 , которая найдет количество способов создать правильное поддерево.
  • Добавьте результат в countBsts.
• После выполнения вышеуказанных шагов распечатайте countBsts.

Временная сложность: O( ²ⁿ )
Вспомогательное пространство: O(1)