96. 不同的二叉搜索树

题目

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

示例 1：

输入：n = 3
输出：5
示例 2：

输入：n = 1
输出：1

代码

class Solution {
public:
    int numTrees(int n) {
        // 思路：dp 
        // 状态表示:dp[i]表示以总节点数为i的二叉搜索树的方案数
        // f(i,n)表示以i为根节点,总节点数为n的二叉搜索树方案数， f(i) = f(i-1)*f(n-i)
        // 则dp[i] = f(0,n) + f(1,n) + f(2,n) + f(3,n).. + f(n,n)
        // f(i) = dp(i-1)*dp(n-i) //根节点两侧左右子树方案数目的乘积
        // 则dp[i] += dp[j-1]*dp[i-j]
        // 状态计算:dp[i] = dp[j-1] * dp[i-j], j∈1~i 
        vector<int> dp(n+1);
        dp[0] = 1;
        for(int i = 1; i <= n; i++)//枚举求出1~n-1之间的所有二叉搜索树的方案数
            for(int j = 1; j <= i; j++)
                dp[i] += dp[j-1] * dp[i-j];
        return dp[n];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18