95. Unique Binary Search Trees II

95. Unique Binary Search Trees II

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

문제

풀이

구현하기 앞서서 이진 검색 트리가 무엇인지 알아야 한다.
이진 검색 트리란 루트 기준으로 왼쪽은 루트보다 반드시 작은 값이 가야하고 오른쪽은 루트보다 반드시 큰 값이 가야한다.

즉 n = 3이라 하였을 때
n = [1, 2, 3]이고 루트가 1이라고 생각해보자

이진검색트리 조건 중 왼쪽 자식 노드는 루트보다 반드시 작어야 하므로 자식 노드로 올 수 있는 것은 없다.

반면에 오른쪽 자식 노드는 루트보다 반드시 커야 하므로 올 수 있는 자식 노드는 2, 3이 된다.

이제 n = [2, 3]을 생각해보자
루트가 2라고 생각했을 때 왼쪽 자식노드는 없고 오른쪽 자식 노드는 3이 된다.
루트가 3이라고 생각했을 때 왼쪽 자식노드는 2가 되고 오른쪽 자식 노드는 없다. 이런 방법으로 구현하였다.

for문에 i 기준으로 dfs(l, i-1)을 하게 되면 i보다 작은 값들에서 탐색하게 되고 dfs(i+1, r)을 하게 되면 i보다 큰 값들에서 탐색하게 되어 이진 검색 조건을 만족하게 된다. 이제 모든 경우를 찾아야 하므로 left, right에 있는 값들을 합하여 리턴해주면 되는데 이제 예외처리를 해주면 된다.
left가 비어있을 경우, right가 비어있을 경우 등 예외처리를 해주고 리턴해주었다.

결과