[leetcode] 96. Unique Binary Search Trees (medium)

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 이 주어질 때 BST 로 만들 수 있는 트리의 개수를 구하는 문제이다. 위의 예시 1번에서의 트리들은 차례대로 다음과 같은 숫자 리스트에서 생성된 BST 이다.

[1, 3, 2] [1, 2, 3] [2, 1, 3](=[2, 3, 1]) [3, 2, 1] [3, 1, 2]

[2, 1, 3] 과 [2, 3, 1] 이 결과적으로는 동일한 트리를 생성하므로 이를 주의해야 한다. 즉, BST 가 가지는 속성이 있기 때문에 숫자 n 으로 리스트 조합을 구하는 방식을 취한다면 중복 트리가 발생할 수 있다.

BST 를 생성하는 방식은 첫번째 숫자를 루트에 두고, 그 이후의 숫자들은 루트 노드부터 시작하여 대소를 구분하여 왼쪽 또는 오른쪽에 위치시킨다. 즉, 루트 노드가 무엇이냐에 따라 그 이후의 노드들은 제자리를 찾아간다.

만약 n = 3 일 때, 루트 노드가 1이면 오른쪽 노드에 2 와 3 이 각각의 순서에 따라 트리를 생성한다는 것이다. 루트 노드 1을 제외하고 생각해봤을 때 남은 노드는 총 두 개이다. 이는 n = 2 일 때의 경우의 수와 동일하다. 따라서 n = 3 에 루트 노드가 1일 경우 n = 2 일 때의 경우의 수 즉, 2개의 경우가 존재한다.

n = 3 에 루트 노드가 2일 경우 왼쪽에는 1, 오른쪽에는 3만 위치할 수 있으므로 경우의 수는 1개이다.

n = 3 에 루트 노드가 3일 경우 왼쪽에 1 과 2 가 위치할 수 있어 2개의 경우의 수가 존재한다.

루트 노드를 제외하고 결국 n = 2 의 경우의 수와 0개일 때의 수를 곱한것과 동일한 결과를 낳는다. 이를 수식으로 정의해보면 다음과 같다.

Code

class Solution:
    def numTrees(self, n: int) -> int:
        dp = [1, 1, 2]
        for i in range(3, n + 1):
            dp.append(0)
            for root in range(1, i + 1):
                dp[i] += dp[root - 1] * dp[i - root]
        return dp[n]

n 을 구하기 위해서는 n - 1 의 값이, n - 1 을 구하기 위해서는 n - 2 의 값이 필요하여 단계적인 속성을 이용한 DP 로 풀이하였다.

• 문제
  • https://leetcode.com/problems/unique-binary-search-trees/description/
• 참고 사이트
  • https://withhamit.tistory.com/403