给定一个整数 � n,有一棵 � n个节点的二叉搜索树,节点值依次为 1 , 2 , … , � 1,2,…,n。求这棵二叉搜索树有多少种可能的形状。 由于输出结果较大,故要求结果对 1 � 9 + 7 1e9+7取模后输出 不失一般性,如果 � = 0 n=0,可能的形状为 1 1
时间: 2024-01-17 16:05:45 浏览: 11
对于二叉搜索树而言,我们可以先确定它的根节点,然后将它的左子树和右子树分别构建出来,最后将它们连在根节点上,就可以构建出一颗二叉搜索树。假设有n个节点,我们可以将它们编号为1, 2, 3, …, n,那么根节点可以是任意一个节点,假设我们选定了第i个节点作为根节点,则其左子树有i-1个节点,右子树有n-i个节点。因此,对于一个n个节点的二叉搜索树而言,其形态数量 = 所有可能的左子树形态数量 × 所有可能的右子树形态数量 × 选择的根节点数量。设n个节点的二叉搜索树形态数量为f(n),则有:
f(n) = ∑(f(i-1) × f(n-i)),其中i∈[1, n]
同时,我们可以发现f(0) = 1,f(1) = 1,因为空树和只有一个节点的树都只有一种形态。因此,我们可以使用动态规划的方法来计算f(n)。在计算过程中,由于结果可能会非常大,我们需要对每次计算的结果取模。时间复杂度为O(N^2)。
以下是Python实现代码:
```python
def numTrees(n: int) -> int:
mod = 1000000007
f = [0] * (n+1)
f[0], f[1] = 1, 1
for i in range(2, n+1):
for j in range(1, i+1):
f[i] = (f[i] + f[j-1] * f[i-j]) % mod
return f[n]
```
测试样例:
输入:3
输出:5
解释:对于3个节点的二叉搜索树而言,其形态数量为5,分别为:
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3