给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种？
思路
二叉搜索树特性：左子树的节点全部小于根节点，右子树的节点全部大于根节点
n=3，则1，2，3轮流当根节点。
当1为根节点时，左子树为空，右子树有两个元素，数量 = 右子树有2个元素的搜索树数量 * 左子树有0个元素的搜索树数量
当2当根节点时，左右子树各有一个元素，数量 = 右子树有1个元素的搜索树数量 * 左子树有1个元素的搜索树数量
当3当根节点时，右子树为空，左子树两个元素，数量 = 右子树有0个元素的搜索树数量 * 左子树有2个元素的搜索树数量
-
定义dp[i]，1~i 为节点组成的二叉搜索树有dp[i]种
-
递归公式，dp[3] = dp[0]*dp[2] + dp[1] * dp[1] + dp[2] * dp[0]，dp[ i ] += dp[ j ] * dp[ i-1-j ]
-
初始化，dp[0]=1, dp[1] =1
-
遍历顺序，dp3 依赖 dp1 和 dp2 所以要先获得dp1 和dp2 的值，从小到大遍历
class Solution:
def numTrees(self, n: int) -> int:
dp = [0] * (n+1)
dp[0]=dp[1]=1
for i in range(2,n+1):
for j in range(i): # j表示左子树的元素个数，i-1-j表示右子树的元素个数
dp[i] += dp[j]*dp[i-1-j]
return dp[-1]
