Leetcode 96. 不同的二叉搜索树

题目描述

给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种？

示例 1:

解法

不妨以 表示 个整数能够组成的二叉搜索树的种类数。则对于 个整数组成搜索树的种类数，需要分别计算出左子树个数为 时二叉树的种类数，左子树个数为 时二叉树的种类数......左子树个数为 时二叉树的种类数，然后相加即可。

若整数个数为 ，当左子树个数为 时，则右子树个数为 ，此时二叉树的种类数为 。

class Solution:
    def numTrees(self, n: int) -> int:
        dp=[1]*(n+1)
        for i in range(2,n+1):
            tmp=0
            for j in range(0,i):
                tmp=tmp+dp[j]*dp[i-1-j]
            dp[i]=tmp
        return dp[n]