96. 不同的二叉搜索树-Toy模板网

这篇具有很好参考价值的文章主要介绍了96. 不同的二叉搜索树。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

1、题目描述

2、思路：动态规划

2.2、确定递推公式

2.3、dp数组初始化

2.4、确定遍历顺序

3、C++实现如下

1、题目描述

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

示例 1：

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

输入：n = 1
输出：1

提示：

1 <= n <= 19

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/unique-binary-search-trees
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2、思路：动态规划

首先仔细都题目，寻找以下n与搜索树数量的关系。

n为1时，搜索树的数量为1；n为2时，搜说树的数量为2。

n为3时，可以有三种情况：

头节点为1时，左子树有0个节点，右子树有2个节点，2个节点的分布情况与n为2时的情况相同。

头节点为2时，左子树有1个节点，右子树有1个节点，1个节点的分布情况与n为1时的情况相同。

头节点为3时，左子树有2个节点，右子树有0个节点，2个节点的分布情况与n为2时的情况相同。

所以我们便可以找到递推公式之间的关系：dp[3] = dp[2] * dp[0] + dp[1] * dp[1] + dp[0] * dp[2]

2.1、确定dp数组及下标的含义

dp[i]表示n=i时的最大搜索树的数量。

2.2、确定递推公式

dp[i] += 以j为头结点的搜索树数量 = dp[以j为头结点左子树节点数量] * dp[以j为头结点右子树节点数量]

j相当于是头结点的元素，从1遍历到i为止。

2.3、dp数组初始化

dp[0]相当于没有子树的情况，自然是1种分布情况。

dp[1]则是以1为头节点，左子树数量为0，右子树数量为0，dp[0]*dp[0] = 1；

所以初始化为dp[0] = 1即可。

2.4、确定遍历顺序

从递归公式：dp[i] += dp[j - 1] * dp[i - j]可以看出，节点数为i的状态是依靠 i之前节点数的状态。文章来源地址https://www.toymoban.com/news/detail-433707.html

3、C++实现如下

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 = 1;j<=i;++j){
                dp[i] += dp[j-1]*dp[i-j];
            }
        }
        return dp[n];
    }
};

到了这里，关于96. 不同的二叉搜索树的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！