96. 不同的二叉搜索树

题目描述

给定一个整数 n，求以 1 … n 为节点组成的二叉搜索树有多少种？

输入: 3
输出: 5
解释:
给定 n = 3, 一共有 5 种不同结构的二叉搜索树:
  1         3     3      2      1
   \       /     /      / \      \
    3     2     1      1   3      2
   /     /       \                 \
  2     1         2                 3

搜索二叉树

搜索二叉树： 左节点比根节点要小， 根节点永远比右节点要小。 左 < 根 < 右

思路

我们以 n = 5 为例子, [1, 2, 3, 4, 5]

  • 当以3为根节点时， 根据左节点永远比根节点小， 那么左节点只能为 [1,2], 右节点为 [4, 5]
    • 当 [1,2] 为左节点时, 又分成了两种情况， 当1为根节点时，2 为右节点；当 2 为根节点时， 1为左节点
    • 当 [4,5] 为右节点时，跟上面类似
  • 当以2 为根节点时，那么 左节点只有为 [1], 右节点为 [3,4,5]
    • [3,4,5] 又可以以 3 或 4 或 5 做为根节点分析
      • 3 为根节点 的时候为两种
      • 4 为根节点的时候有一种
      • 5 为根节点的时候又两种

所以你会发现节点有两个的时候 f(2) = 2; f(1) = 1, 左右节点相乘就可以得到总数了
所以
f(2) = f(0) * f(1) + f(1) * f(0)
f(3) = f(0) * f(2) + f(1) * f(1) + f(2) * f(0)
f[4] = f(0) * f(3) + f(1) * f(2) + f(2) * f(1) + f(3) * f(0)

代码

var numTrees = function(n) {
    const dp = new Array(n + 1).fill(0);
    dp[0] = 1;
    dp[1] = 1;

    for (let i = 2; i <= n; ++i) {
        for (let j = 1; j <= i; ++j) {
            dp[i] += dp[j - 1] * dp[i - j];
        }
    }
    return dp[n];
};