题目
Given n, how many structurally unique BST’s (binary search trees) that store values 1 … n?
解题思路
- 如果确定了根，那么就确定了左右子树有哪些节点，那么就可以简化成两个子树的BST的个数相乘，再枚举每个数作为根
- 这个过程的结果就是卡特兰数的第n项
代码
class Solution:
def numTrees(self, n: int) -> int:
res = [0] * (n + 1)
res[0] = res[1] = 1
for i in range(2, n + 1):
tmp = 0
for j in range(0, i):
tmp += res[j] * res[i - 1 - j]
res[i] = tmp
return res[n]
class Solution:
def numTrees(self, n: int) -> int:
C = 1
for i in range(n):
C = C * 2 * (2 * i + 1) // (i + 2)
return C
