Skip to content

0096.不同的二叉搜索树

96 不同的二叉搜索树

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

为什么没有想到解法？

  1. 动态规划不熟练。这个题目的递推公式不能一步得出，需要借助一个转换函数，转换后再递推
  2. 笛卡尔积不懂（笛卡尔积就是求两个集合的笛卡尔积）
  3. 如何使用代码（js）实现笛卡尔积

如果自己钻牛角尖，1天也可能想不出来这个解法

算法1：DP 算法

时间复杂度 O(n * n) 空间复杂度 O(n)

https://leetcode-cn.com/problems/unique-binary-search-trees/solution/bu-tong-de-er-cha-sou-suo-shu-by-leetcode-solution/

基本思路：能写多少写多少

二叉搜索树长度是N，那么我们假设根节点是 1——N 中的任何一个

也就是 G(n) = 叠加 1 —— N 当 i 是根节点的情况 设为 F（i， n） 表示以 i 为根节点满足的二叉搜索树的情况

如果根节点是i，那么根节点固定，左子树和右子树不同，左子树是 i - 1 右子树是 n - i

也就是 F（i， n） = G(i - 1) * G(n - i)

然后把上面两个公式转换，G(n) = (1 - N) G(i - 1) * G(n - i) 就是递推公式

如果需要计算N，那么需要依次计算前面的项，动态规划即可

numTrees = (k) => {
  // 初始化递推数组
  // 因为我们需要计算第K个，那么就是数组的第 K + 1 项，所以数组长度需要加1
  let res = new Array(k + 1);
  // 如果是0或者1个节点，那么就只有一个情况（空树，或者只有一个根节点）
  res[0] = 1;
  res[1] = 1;
  // 开始递归计算N
  // 外循环的 i 表示第 N 项
  for (let i = 2; i <= k; i++) {
    // res[i] 初始化为0， 然后叠加
    res[i] = 0;
    // 内循环 N 表示求和，从 1 加到当前的 i
    for (let n = 1; n <= i; n++) {
      // 注意这里是 += 不是 =
      res[i] += res[i - 1] * res[n - i];
    }
  }
  return res[k];
}

算法2：数学排列组合：卡特兰数

https://baike.baidu.com/item/%E5%8D%A1%E7%89%B9%E5%85%B0%E6%95%B0/6125746

这个了解即可，短期内想不到（需要数学基础等）

时间复杂度 O (n)

catalan = (n) => {
  let C = 1;
  for (let i = 0; i < n; i++) {
    C = C * 2 * (2 * i + 1) / (i + 2);
  }
  return C;
}