96. [✔][M]不同的二叉搜索树

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

示例 1：

输入：n = 3
输出：5

示例 2：

输入：n = 1
输出：1

提示：

• 1 <= n <= 19

---

题解:

二叉搜索树

// @lc code=start
function numTrees(n: number): number {
    let memo = new Array(n + 1).fill(1).map(() => new Array(n + 1).fill(0));

    let count = (low: number, high: number): number => {
        if (low > high) {
            return 1;
        }

        if (memo[low][high] !== 0) {
            return memo[low][high];
        }

        let res = 0;
        // 遍历[low,high]，每个分别作为根节点
        for (let i = low; i <= high; i++) {
            let left = count(low, i - 1);
            let right = count(i + 1, high);
            res += left * right;
        }

        memo[low][high] = res;;
        return res;
    }
    return count(1, n);
};
// @lc code=end