96. Unique Binary Search Trees

[Tcdian]

96. Unique Binary Search Trees

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

Example

Input: 3
Output: 5
Explanation:
Given n = 3, there are a total of 5 unique BST's:

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

[Tcdian]

Solution 1

• JavaScript Solution

/**
 * @param {number} n
 * @return {number}
 */
var numTrees = function(n) {
    const cache = new Map();
    return recursiveCalcTrees(1, n);

    function recursiveCalcTrees(start, end) {
        if (start > end) {
            return 1;
        }
        if (cache.has(end - start)) {
            return cache.get(end - start);
        }
        let result = 0;
        for (let i = start; i <= end; i++) {
            const leftNums = recursiveCalcTrees(start, i - 1);
            const rightNums = recursiveCalcTrees(i + 1, end);
            result += leftNums * rightNums;
        }
        cache.set(end - start, result);
        return result;
    }
};

• TypeScript Solution

function numTrees(n: number): number {
    const cache: Map<number, number> = new Map();
    return recursiveCalcTrees(1, n);

    function recursiveCalcTrees(start: number, end: number) {
        if (start > end) {
            return 1;
        }
        if (cache.has(end - start)) {
            return cache.get(end - start) as number;
        }
        let result = 0;
        for (let i = start; i <= end; i++) {
            const leftNums = recursiveCalcTrees(start, i - 1);
            const rightNums = recursiveCalcTrees(i + 1, end);
            result += leftNums * rightNums;
        }
        cache.set(end - start, result);
        return result;
    }
};

Solution 2

• JavaScript Solution

/**
 * @param {number} n
 * @return {number}
 */
var numTrees = function(n) {
    const dp = new Array(n + 1).fill(0);
    dp[0] = 1;
    for (let i = 1; i <= n; i++) {
        for (let j = 0; j < i; j++) {
            dp[i] += dp[j] * dp[i - j - 1];
        }
    }
    return dp[n];
};

• TypeScript Solution

function numTrees(n: number): number {
    const dp: number[] = new Array(n + 1).fill(0);
    dp[0] = 1;
    for (let i = 1; i <= n; i++) {
        for (let j = 0; j < i; j++) {
            dp[i] += dp[j] * dp[i - j - 1];
        }
    }
    return dp[n];
};