LC96. 不同的二叉搜索树

今天思考 LeetCode 题目:不同的二叉搜索树[1]

#题目描述

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

#题解[2]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
/**
 * @param {number} n
 * @return {number}
 */
var numTrees = function(n) {
    const G = new Array(n + 1).fill(0);
    G[0] = 1;
    G[1] = 1;

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

使用了动态规划的办法。


  1. https://leetcode-cn.com/problems/unique-binary-search-trees/ 

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