96. Unique Binary Search Trees

难度: Medium

题目描述

Given an integer n, return the number of structurally unique BST's (binary search trees) which has exactly n nodes of unique values from 1 to n.

 

Example 1:

Input: n = 3
Output: 5

Example 2:

Input: n = 1
Output: 1

 

Constraints:

• 1 <= n <= 19

解题思路

代码实现

解决方案

java

import java.math.BigInteger;
class Solution {
     public   int numTrees(int n) {

        BigInteger numerator = factorial(2 * n);
        BigInteger denominator = factorial(n).multiply(factorial(n + 1));
        return numerator.divide(denominator).intValue();
    }
    public static BigInteger factorial(int n) {
        BigInteger result = BigInteger.ONE;
        for (int i = 1; i <= n; i++) {
            result = result.multiply(BigInteger.valueOf(i));
        }
        return result;
    }
}