注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

HT·生活

123

 
 
 

日志

 
 

ex96 Unique Binary Search Trees  

2015-05-17 20:18:17|  分类: leetcode |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
我能说这题我能想到递归,但是就是那个递推公式想不出来么~~

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
关于构造这种特殊的树,确实比较恶心,这个只是让输出个数,下一个让直接输出所有的树~~本题见c代码

/*
* 好吧!我表示这题真的没有什么思路,只知道肯定是有递推公式的
* 用动态规划额。。。。。。。。
*/


/*
* 当 n=1的时候根节点只有一个选择 1
* 当 n=2的时候根节点有两种选择,
* 当 n=3的时候根节点又3中选择
* 直观地可以想想,当n个节点的时候,节点固定的时候,
* 左右子树的BST乘积就是当前root的BST的数量
*/

int numTrees(int n) {
if (n <= 0)
return 1;
int i, j;
int *result = (int*)malloc((n+1)*sizeof(int));
result[0] = 1;
result[1] = 1;
result[2] = 2;
for (i = 3; i <= n; i++)
{
//root节点固定
result[i] = 0;
for (j = 0; j < i; j++)
{
//假设左子树分配i个节点,右子树分配的节点数量为 n-j-1
result[i] += result[j] * result[i - j - 1];
}
}

int num = result[n];
free(result);
result = NULL;
return num;
}

update java version 2015/12/7

public class UniqueBinarySearchTrees {
public int numTrees(int n) {
return helper(n);
}
private int helper(int n) {
if (n <= 0) {
return 1;
}
int[] result = new int[n + 1];
result[0] = 1;
result[1] = 1;
//result[2] = 2;
for (int i = 2; i <= n; ++i) {
result[i] = 0;
for (int j = 0; j < i; ++j) {
result[i] += result[j] * result[i - j -1];
//左子树分j个节点,右子树分i-j-1个节点
}
}
return result[n];
}
}


  评论这张
 
阅读(9)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017