首页 > 代码库 > 【leetcode】Unique Binary Search Trees
【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];
1 class Solution { 2 public: 3 int numTrees(int n) { 4 5 if(n==0||n==1) 6 { 7 return 1; 8 } 9 vector<int> f(n+1);10 11 f[0]=1;12 f[1]=1;13 14 for(int i=2;i<=n;i++)15 {16 f[i]=0;17 for(int j=0;j<i;j++)18 {19 f[i]+=f[j]*f[i-j-1];20 }21 }22 23 return f[n];24 }25 };26
【leetcode】Unique Binary Search Trees
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。