96. Unique Binary Search Trees

96. Unique Binary Search Trees

https://leetcode.com/problems/unique-binary-search-trees/

문제

풀이

Example1에서 생각해보자
root노드 기준으로 left, right를 나누어 생각하자, root노드를 제외하면
1. left = 2, right = 0
2. left = 1, right = 1
3. left = 0, right = 2로 생각할 수 있다.
그럼 n = 2일 때를 생각해보자
root노드는 제외하고 생각해야 하므로
1. left = 1, right = 0
2. left = 0, right = 1로 생각할 수 있고, 개수가 1일 때에는 당연히 1일 수 밖에 없으므로 결국 2가 리턴이 될 것이다.
다시 n = 3일 때를 생각해보자
n = 2일 때는 2인 것을 알았으므로
(21) + (11) + (1*2) = 5가 될 것이다.
이런식으로 n까지 구하면 쉽게 구할 수 있다.

결과