leetcode--96--不同的二叉搜索树

给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。

示例 1：

输入：n = 3
输出：5
示例 2：

输入：n = 1
输出：1

提示：

1 <= n <= 19

链接：https://leetcode-cn.com/problems/unique-binary-search-trees

思路：
1、公式大法。C(0)=1, C(n+1)= 2(2n+1)/(n+2)*C(n)

Python代码：

class Solution(object):
    def numTrees(self, n):
        """
        :type n: int
        :rtype: int
        """
        # C(0)=1, C(n+1)= 2(2n+1)/(n+2)*C(n)
        ans = 1
        for i in range(n):
            ans = 2*ans*(2*i+1)/(i+2)
        return ans

Java代码：

class Solution {
    public int numTrees(int n) {
        // C(0)=1, C(n+1)= 2(2n+1)/(n+2)*C(n)
        long ans = 1;
        for (int i=0; i<n; i++){
            ans = 2*ans*(2*i+1)/(i+2);
        }
        return (int)(ans);
    }
}