96. 不同的二叉搜索树 (opens new window)

Description

Difficulty: 中等

Related Topics: 树 (opens new window), 二叉搜索树 (opens new window), 数学 (opens new window), 动态规划 (opens new window), 二叉树 (opens new window)

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

示例 1：

输入：n = 3
输出：5

示例 2：

输入：n = 1
输出：1

提示：

• 1 <= n <= 19

Solution

Language: JavaScript

什么是二叉搜索树（BST）？

其实这个概念非常简单，二叉树里每个节点都是一个爸爸，每个爸爸有两个儿子而二叉“搜索”树就是要满足一个额外的条件：所有左儿子的数字都比爸爸数字小，所有右儿子的数字都比爸爸数字大。

动态规划: 将二叉树的种类n分解成左树和右树的子问题

/**
 * @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]
};

var numTrees = function(n) {
 let res = 1;
 for (let i = 1; i <= n; i++) {
  res = res * 2 * (2 * i + 1) / (i + 2)
 }
 return res;
}