首页 > 代码库 > [leetcode] Unique Binary Search Trees (python)
[leetcode] 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
题目的意思是，给定一个节点数n，问可以组合成多少种二叉树。
这里提供两种解法，递归法 和 动态规划法
递归法：
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
动态规划法：
def numTrees(self, n): if n ==1 or n ==0: return 1 dp =[] i =1 while i <= n+1: dp.append(0) i = i + 1 dp[0] =1 dp[1] =1 i =2 while i <=n: j =1 sumVal =0 while j <= i: sumVal = sumVal + dp[j-1]*dp[i-j] j =j + 1 dp[i] =sumVal i = i + 1 return dp[n]
[leetcode] Unique Binary Search Trees (python)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。