不同的二叉搜索树（LeetCode-96）

7. 不同的二叉搜索树（LeetCode-96）

题目

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

示例 1：

输入：n = 3
输出：5

示例 2：

输入：n = 1
输出：1

提示：

1 <= n <= 19

思路

这里用代码随想录的图分析一下

n = 1

n = 2

n = 3

可以分3种情况

1.元素1为头结点时，没有比1小的元素了，所以左子树为空，右子树元素个数为二，就有 dp[2] 种组合。为什么是 dp[2] 种，题目不是说是由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种吗？这里呢其实大家要明白 dp[i] 的含义，也就是先定dp数组——i 个不同元素节点组成的互不相同的二叉搜索树有 dp[i] 种。我这里去掉了节点值从 1 到 n ，因为对于元素个数为2的二叉搜索树来说，无论它的元素值是 1 ， 2  还是 2 ， 3，排列组合的结果都是一样的！

2.元素2为头结点时，左子树元素个数为一，右子树元素个数也为一

3.元素3为头结点时，左子树元素个数为二，右子树元素个数也为零

4.所以 d p [ 3 ] = d p [ 2 ] ∗ d p [ 0 ] + d p [ 1 ] ∗ d p [ 1 ] + d p [ 0 ] ∗ d p [ 2 ]

五部曲

1.dp[i] 含义： i 个不同元素节点组成的互不相同的二叉搜索树有 dp[i] 种

2.变量 j 从 0 遍历至 i-1 ，dp[i] 初值为零

d p [ i ] = d p [ i ] + d p [ j ] ∗ d p [ i − j − 1 ]

3.dp[0]=1 从定义上来讲，空节点也是⼀颗⼆叉树，也是⼀颗⼆叉搜索树

4.节点数为i的状态是依靠 i之前节点数的状态,所以从前往后

5.样例

代码展示

class Solution
{
public:
    int numTrees(int n)
    {
        vector<int> dp(n + 1);
        dp[0] = 1;
        for (int i = 1; i <= n; i++)
        {
            for (int j = 0; j < i; j++)
            {
                dp[i] += dp[j] * dp[i - j - 1];
            }
        }
        return dp[n];
    }
};