[leetcode] Unique Binary Search Trees (python)
浏览数：29 /
时间：2015年06月08日
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]
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
