一、题目

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

二、示例

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

示例二
输入：n = 1
输出：1

三、思路
什么是二叉搜索树？

1、若任意结点的左子树不空，则左子树上所有结点的值均不大于它的根结点的值。
2、若任意结点的右子树不空，则右子树上所有结点的值均不小于它的根结点的值。
3、任意结点的左、右子树也分别为二叉搜索树。

本题思路：

假设0个节点的时候，存在1种形态就是空。
一个节点存在1中形态
两个节点存在两种形态: 以[3,1]为例： 根节点为3：则左子树为1，右子树为null
								根节点为1，则右子树为3，左子树为null.
三个节点是：左子树可以为0个，此时右子树可以为2个
		左子树可以为2个，此时右子树可以为1个
		左子树可以为1个，此时右子树可以为1个
四个节点是：......

四、代码

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

五、总结