力扣题解（不同的二叉搜索树）
给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
思路：
首先明确二叉搜索树的概念，这和本题息息相关，如果不是二叉搜索树而是别的树，做法可能就会不一样了。二叉搜索树是对于任意节点k，要求所有左孩子节点小于k，右节点大于k。因此对于每个节点，可以清晰的把所有可以插入的节点分到左右子树中。
dp[i]表示有i个节点的种树（对于这种顺序不固定，对每个数有一定选择的题貌似很喜欢让dp表示总的个数而不是前i个个数什么的？）。dp[i]的组成是对于j属于1到i，所有dp[j-1]*dp[i-j]的和，可以看成是i个节点就是1到i所有的数，取一个数j为中间，然会分成左右子树两部分，左边的个数是j-1个，右边个数是i-j个，那就是dp[j-1]*dp[i-j]啦。需要注意的是，存在某一侧没有节点，即可能有左子树或者右子树是空树的情况，此时就是dp[0]，因为是用的乘法，所以dp[0]=1，认为空树就一种组合方法。
class Solution {
public:
int numTrees(int n) {
vector<int>dp(n+1,0);
dp[0]=1;
for(int i=1;i<=n;i++) //i表示节点个数
{
for(int j=1;j<=i;j++)
{
int l=dp[j-1],r=dp[i-j];
dp[i]+=l*r;
}
}
return dp[n];
}
};原文地址：https://blog.csdn.net/yyssas/article/details/140609797
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！