題目如下：
首先二叉搜索樹(shù)與二叉樹(shù)的區(qū)別在于BST一定是二叉樹(shù)，并且結(jié)點(diǎn)信息是關(guān)鍵碼（可能還帶有記錄的索引），并且BST中關(guān)鍵碼無(wú)重復(fù)，左子樹(shù)如果存在，其所有的關(guān)鍵碼一定小于根，右子樹(shù)如果存在，其所有關(guān)鍵碼一定大于根，左右子樹(shù)自然也是BST，因此有特性中序遍歷序列單調(diào)遞增
這道題應(yīng)該是做題兩個(gè)星期以后解題最快的一道了，５分鐘提交。這道題目咋一看沒(méi)什么思路，也沒(méi)什么狀態(tài)，動(dòng)作之類的，但是畫(huà)一畫(huà)圖馬上就知道該怎么做了，n個(gè)數(shù)，分析它的子樹(shù)，假設(shè)左邊有i個(gè)數(shù)，（這i個(gè)數(shù)都比他?。┠敲从疫吘陀衝-1-i個(gè)數(shù)（同理都比它大），那么很明顯,變成了兩個(gè)子問(wèn)題，dp[n]=dp[i]*dp[n-1-i],i=0到n-1求和，我們不斷分解到最后，發(fā)現(xiàn)dp[0]=dp[1]=1，dp[2]已經(jīng)可以由dp[0]和dp[1]得出，為了減少計(jì)算量，用一個(gè)數(shù)組記錄之前計(jì)算得到的dp，避免重復(fù)計(jì)算，此題得解。
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)
以上是自己的解法，看了一下討論，大部分都是這個(gè)想法，不過(guò)看到了一個(gè)遞歸的解法，的確，這個(gè)題，與斐波那契有相似之處，都可以用遞歸來(lái)求解
題解如下：
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
