题目如下：
首先二叉搜索树与二叉树的区别在于BST一定是二叉树，并且结点信息是关键码（可能还带有记录的索引），并且BST中关键码无重复，左子树如果存在，其所有的关键码一定小于根，右子树如果存在，其所有关键码一定大于根，左右子树自然也是BST，因此有特性中序遍历序列单调递增
这道题应该是做题两个星期以后解题最快的一道了，５分钟提交。这道题目咋一看没什么思路，也没什么状态，动作之类的，但是画一画图马上就知道该怎么做了，n个数，分析它的子树，假设左边有i个数，（这i个数都比他小）那么右边就有n-1-i个数（同理都比它大），那么很明显,变成了两个子问题，dp[n]=dp[i]*dp[n-1-i],i=0到n-1求和，我们不断分解到最后，发现dp[0]=dp[1]=1，dp[2]已经可以由dp[0]和dp[1]得出，为了减少计算量，用一个数组记录之前计算得到的dp，避免重复计算，此题得解。
class Solution:
def numTrees(self, n):
"""
:type n: int
:rtype: int
"""
if n==0 or n==1:
return 1
dp=[0]*(n+1)
dp[0]=1
dp[1]=1
for i in range(2,n+1):
k=0
for j in range (i):
k=dp[j]*dp[i-1-j]+k
dp[i]=k
return dp[n]
solution=Solution
k=solution.numTrees(solution,2)
print(k)
以上是自己的解法，看了一下讨论，大部分都是这个想法，不过看到了一个递归的解法，的确，这个题，与斐波那契有相似之处，都可以用递归来求解
题解如下：
class Solution:
def __init__(self):
self.dic = {}
def numTrees(self, n):
if n <= 1:
return 1
elif n in self.dic:
return self.dic[n]
else:
out=0
for i in range(0, n):
out += ( self.numTrees(i) * self.numTrees(n-1-i) )
self.dic[n] = out
return out
网友评论