LeetCode - 96. Unique Binary Search Tree

알고리즘/알고리즘 문제 복기

내일도무사히 2021. 5. 18. 12:20

Unique한 바이너리 서치 트리의 개수를 구하는 문제

처음에는 바이너리 서치 트리에 대해서 생각을 안해서 못풀었었다.

바이너리 서치 트리는 루트보다 큰 값은 오른쪽에 저장하고 작은 값은 왼쪽에 저장하는 방식의 자료구조라고 한다.

Root가 x라면 바이너리 서치 트리의 특성에 따라서

왼쪽에는 x보다 작은 값만 올 수 있고

오른쪽에는 x보다 큰 값만 올 수 있다

만약 N=3이고 루트도 3이라면 왼쪽에는 2이하의 값들만 나오고 오른쪽에는 아무값도 나올 수 없다

즉 g(x)를 루트가 x일때 가질 수 있는 Unique Binary Search의 경우의 수라고 한다면

g(x) = g(m) * g(n)이 된다.

따라서 다음과 같이 정리 할 수 있게 된다.

이를 DP를 이용해 풀어내면 된다.