[Leetcode/Python] 96. Unique Binary Search Trees

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

Unique Binary Search Trees - LeetCode

 

 

 

🤔 문제. 

n 개의 노드가 주어졌을 때, BST를 구성할 수 있는 경우의 수를 구하는 문제이다. 

 

🤗 풀이. 

처음에는 BST를 모두 구현을 해야하나...? 라는 생각이 들었다. (그러나 leetcode 특성상 그런 무식한 문제는 잘 없다.)
하지만 이내 이 문제는 다이나믹 프로그래밍으로 해결할 수 있다는 것을 알 수 있었다.

BST의 성질을 생각해보자.

1. 노드에 저장된 키는 유일하다.
2. 부모의 키가 왼쪽 자식 노드의 키보다 크다.
3. 부모의 키가 오른쪽 자식 노드의 키보다 작다.
4. 왼쪽과 오른쪽 서브 트리도 BST이다.

여기서 주목할 점은 왼쪽과 오른쪽의 서브 트리도 BST라는 점이다. 

즉, 갯수가 n인 BST를 구하기 위해서 루트 노드를 고정해두면 좌, 우 자식 노드는 BST이고, 개수는 최대 n-1이다.

n = 4를 예로 들어보자. (우리는 leetcode 예시에서 n=3일 때 5개의 BST가 구성되는 것을 알고있다.)

• Root Node: 1 >> 왼쪽 자식 노드의 개수=0 and 오른쪽 자식 노드의 개수=3 >> 경우의 수: 1*5=5
• Root Node: 2 >> 왼쪽 자식 노드의 개수=1 and 오른쪽 자식 노드의 개수=2 >> 경우의 수: 1*2=2
• Root Node: 3 >> 왼쪽 자식 노드의 개수=2 and 오른쪽 자식 노드의 개수=1 >> 경우의 수: 2*1=2
• Root Node: 4 >> 왼쪽 자식 노드의 개수=3 and 오른쪽 자식 노드의 개수=0 >> 경우의 수: 5*1=5

따라서 총 경우의 수는 14가 된다.

그리고 일반식으로 전개하면 아래와 같다.

dp(n) = dp(n-1)*dp(0) + dp(n-1-1)*dp(1) + ... + dp(0)dp(n-1)

 

 

이를 코드로 구현해보자!

👉 Python

 

👉 Scala