96.不同的二叉搜索树

2020-06-03

不同的二叉搜索树

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

题解:

思路1：动态规划

/**
 * @param {number} n
 * @return {number}
 */
var numTrees = function (n) {
  let dp = new Array(n + 1).fill(0); // dp[n]的值就是n对应的二叉树的可能 从小到大求得每一项n的值存到dp
  dp[0] = 1; // 当n=0时有1种可能 当n=2时有两种
  dp[1] = 1;
  dp[2] = 2;

  for (let i = 3; i <= n; i++) {
    // 先求当i = 3 时 dp[i] 有多少种可能
    // 首先将1作为根节点 1 的左边有 dp[1-1] 种可能 右边有 dp[3-1] 种可能 所以1为根节点的有 dp[0] * dp[2] 种
    // 再以2作为根节点 2 的左边有 dp[2-1] 种可能 右边有 dp[3-2] 种可能 所以1为根节点的有 dp[1] * dp[1] 种
    // 再以3作为根节点 3 的左边有 dp[3-1] 种可能 右边有 dp[3-3] 种可能 所以1为根节点的有 dp[2] * dp[0] 种
    // 求得 dp[3] = 2 + 1 + 2;

    // 然后i自加 算i=4时 dp[i]的值
    for (let j = 1; j <= i; j++) {
      dp[i] += dp[j - 1] * dp[i - j];
    }
  }
  return dp[n]; // 第N项的值就是可能性
};