【leetcode】Unique Binary Search Trees

时间:2023-03-09 18:45:07
【leetcode】Unique Binary Search Trees

Unique Binary Search Trees

Given n, how many structurally unique BST's (binary search trees) that store values 1...n?

For example,
Given n = 3, there are a total of 5 unique BST's.

   1         3     3      2      1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
推导出递推公式即可:
对于1个元素来说,f[1]=1;
对于2个元素来说,有两种f[2]=2;
对于3个元素来说,
1) 把1作为根节点,则2,3都连在右边,共有2种
2)把2作为根节点,则1,2必须一个在左边,一个在右边,共1种
3)把3作为根节点,则2,3必须在左边,共有2种
把i作为根节点时,我们有前面i-1个元素放在左边,后面i+1到n个元素放在右边
所以对于f[n]我们有以下的公式:
f[n]=f[n-1]+f[1]f[n-2]+f[2]f[n-3]+......+f[n-2]f[1]+f[n-1];
引入f[0]=1,f[1]=1;
则f[n]=f[0]f[n-1]+f[1]f[n-2]+f[2]f[n-3]+......+f[n-2]f[1]+f[n-1]f[0];
 class Solution {
public:
int numTrees(int n) { if(n==||n==)
{
return ;
}
vector<int> f(n+); f[]=;
f[]=; for(int i=;i<=n;i++)
{
f[i]=;
for(int j=;j<i;j++)
{
f[i]+=f[j]*f[i-j-];
}
} return f[n];
}
};