[leetcode] 96. Unique Binary Trees

Unique Binary Search Trees - LeetCode

 

Unique Binary Search Trees - LeetCode

문제설명

노드의 갯수가 주어졌을 때 만들 수 있는 Binary Search Tree 의 갯수를 구하는 문제이다

풀이

Catalan Number에 대해 들어봤었다면 이 문제를 쉽게 풀 수 있었을 것이다.

조합론에서 나오는 개념인데, 아래와 같은 수식으로 표현된다

$$C_n=\Sigma^{n-1}_0 C_i C_{n-1-i}=\frac{1}{n+1}\binom{2n}{n}$$

카탈란 수를 활용하는 예시로

 

n 쌍의 괄호를 이용해서 만들 수 있는 서로 다른 괄호의 수 역시 카탈란 수를 따른다.

예를 들어 4쌍의 괄호를 생각해보면

(num(0쌍)) * num(3쌍)

(num(1쌍)) * num(2쌍)

(num(2쌍))* num(2쌍)

(num(2쌍)) * num(1쌍)

(num(3쌍)) * num(0쌍)

이렇게 5가지 경우로 나누어서 생각할 수 있다.

 

Binary Search Tree도 마찬가지로 Root Node를 기준으로 왼쪽 subtree와 오른쪽 subtree의 경우의 수를 나열해보면 아래와 같다.

num(0)*num(n-1)

num(1)*num(n-2)

...

num(n-1)*num(0)