# 二叉搜索树的特点是左子树小于根节点，右子树大于根节点。
# 因此当根节点为i的时候，左子树的值为1：i-1，右子树为i+1：n
# 当节点为n的时候所有的能够组成的树为左子树个数乘以右子树个数。
class Solution:
    def numTrees(self, n: int) -> int:
        dp = [0] * (n + 1)
        dp[0] = 1
        for index1 in range(1,n + 1):
            for index2 in range(1,index1 + 1):
                # dp[index2 - 1]代表左子树个数
                # dp[index1 - index2]代表右子树个数
                dp[index1] += dp[index2 - 1] * dp[index1 - index2]
        return dp[n]
A = Solution()
print(A.numTrees(3))