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

思路

  1. 《95 - 不同的二叉搜索树 II》 的简化版
  2. 暴力做法: 沿用 95 代码,返回 length 即可(但运行时出现了 bad_alloc 的错误)
  3. 可以直接用动态规划的思路解决此问题
  4. dp[0] = 1, dp[1] = 1, dp[n + 1] = SUM(dp[i] * dp[n - i])
1
2
3
4
5
6
7
8
9
10
11
var numTrees = function (n) {
const dp = new Array(n + 1).fill(1)
for (let i = 0; i < n; ++i) {
let sum = 0
for (let j = 0; j <= i; ++j) {
sum += dp[j] * dp[i - j]
}
dp[i + 1] = sum
}
return dp[n]
}