5. 不同的二叉搜索树（96）

一、题目内容 中等

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

示例1：

输入：n = 3 输出：5

示例2：

输入：n = 1 输出：1

提示：

• 1 <= n <= 19

  二、解题思路

  我们先画画图，看能不能找到规律。从节点最少的开始画起。
  
  n 为 1 的时候有一棵树，n 为 2 有两棵树，这个是很直观的。
  
  当 1 为头节点的时候，我们可以发现 2、3 节点就是 n = 2 时的布局，dp[2]
  当 2 为头节点的时候，我们可以发现 1、3 节点就是 n = 1 时的布局，dp[1]
  当 3 为头节点的时候，我们可以发现 1、2 节点就是 n = 2 时的布局，dp[0]

  dp[3]，就是 元素 1 为头结点搜索树的数量 + 元素 2 为头结点搜索树的数量 + 元素 3 为头结点搜索树的数量 元素 1 为头结点搜索树的数量 = 右子树有 2 个元素的搜索树数量 左子树有 0 个元素的搜索树数量 元素 2 为头结点搜索树的数量 = 右子树有 1 个元素的搜索树数量 左子树有 1 个元素的搜索树数量 元素 3 为头结点搜索树的数量 = 右子树有 0 个元素的搜索树数量 * 左子树有 2 个元素的搜索树数量

那么我们令 i 为节点数，dp[i]表示 i 个节点下，能形成的二叉搜索树个数。
初始化 dp[0] = 1、dp[1] = 1、dp[2] = 2
当 n = 3 时，dp[3]与之前 dp 的关系。
dp[3] = dp[2] * dp[0] + dp[1] * dp[1] + dp[0] * dp[2]

在上面的分析中，其实已经看出其递推关系，
dp[i] += dp[以j为头结点左子树节点数量] * dp[以j为头结点右子树节点数量]
所以递推公式：dp[i] += dp[j - 1] * dp[i - j]
（j-1 为j为头结点左子树节点数量，i-j 为以j为头结点右子树节点数量）

三、具体代码

/**
 * @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 = 1; j <= i; j++) {
      dp[i] += (dp[j - 1] * dp[i - j])
    }
  }
  return dp[n]
};
/**
 * 时间复杂度：O(n^2)
 * 空间复杂度：O(n)
 */

四、其他解法