[LeetCode] 96. Unique Binary Search Trees

Given an integer n, return the number of structurally unique BST's (binary search trees) which has exactly n nodes of unique values from 1 to n.

 

Example 1:

Input: n = 3
Output: 5

Example 2:

Input: n = 1
Output: 1

 

Constraints:

• 1 <= n <= 19

반응형

---

숫자 n이 주어졌을 때 1~n까지 숫자를 이용하여 유니크한 BST 구조를 몇개가 존재하는지 묻는 문제이다.

이 문제는 카탈란 수(Catalan number) 수열로 해결할 수 있다.

Catalan number

카탈란 수 점화식

카탈란 수 점화식을 재귀함수로 구현하게 되면 아래 코드와 같다.

class Solution:
    def numTrees(self, n: int) -> int:
        # catalan_num
        def calcul(num: int) -> int:
            if num == 0:
                return 1
            else:
                return calcul(num - 1) * 2 * (2 * num + 1) // (num + 2)

        return calcul(n - 1)

 

 

문제 출처 : https://leetcode.com/problems/unique-binary-search-trees/

Unique Binary Search Trees - LeetCode

Github : https://github.com/kkkkang1009/leetcode/blob/master/leetcode_96.py

GitHub - kkkkang1009/leetcode: leetcode