首页 > 代码库 > Unique Binary Search Trees 三种解法 python
Unique Binary Search Trees 三种解法 python
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
递归版，也是AC
class Solution: @return an integer # 2014年10月9日，需要改为dp，这个是递归的 def numTrees(self, n): if n ==1 or n ==0: return 1 else: i=1 sum=0 while i<=n: sum =sum+self.numTrees(i-1)*self.numTrees(n-i) i =i+1 return sum
dp版，当然也能AC
class Solution: # @return an integer def numTrees(self, n): dp = [0 for i in xrange(n+1)] dp[0] = 1 for nodeNum in xrange(1, n+1): for leftSubNum in xrange(nodeNum): dp[nodeNum] += dp[leftSubNum] * dp[nodeNum - 1 - leftSubNum] return dp[n]
代码是抄http://chaoren.is-programmer.com/posts/42907.html的
最后是利用catalan数来求解
#卡塔兰版class Solution: # @return an integer def numTrees(self, n): catalan =[1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190] return catalan[n]
这个时间复杂度还是o(1)呢，/窃笑
Unique Binary Search Trees 三种解法 python
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。