提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档
目录
提示：以下是本篇文章正文内容，下面案例可供参考
一、背景介绍
给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数
输入：n = 3
输出：5
根节点分别为1、2、3时，一共有五种情况，分别是
1）根节点为1，先给节点2，再给节点3
2）根节点为1，先给节点3，再给节点2
3）根节点为2，分别给节点1和3
4）根节点为3，先给节点1，再给节点2
5）根节点为3，先给节点2，再给节点1
输入：n = 1
输出：1
二、解题思路
假设我们有一个由 i 个节点组成的二叉搜索树，我们选择其中一个节点作为根节点。设根节点的值为 j，那么：
左子树将包含小于 j 的所有节点，即 1 到 j-1 的节点，因此左子树有 j-1 个节点
右子树将包含大于 j 的所有节点，即 j+1 到 i 的节点，因此右子树有 i-j 个节点
由于二叉搜索树的性质，左子树和右子树也必须是二叉搜索树。因此，左子树的种数为 dp[j-1]，右子树的种数为 dp[i-j]。
这个地方有点儿绕，突然就从二叉树跳跃到数组值了，解释一下是怎么来的。
这个地方需要转换一下思路，就把j-1当成j-1个节点的组合数，i-j当成i-j个节点的组合数，举个例子，例如j为2时，左子树一共有2-1=1个节点，那么组合方式就是1；例如j为3时，左子树一共有3-1=2个节点，那么组合方式就是2，依此类推。就把它当作从1开始的几个数，然后自由组合。
所以我们并不是在求指定的一些数字的组合，而是转变为求几个从1开始的数字的组合，这么看就简单多了。
刚好这些组合数是我们前边已经计算过的，所以直接利用。
代码示例：
public void test() {
int n = 3;
int[] dp = new int[n + 1];
// 初始化0个节点和1个节点的组合数
dp[0] = dp[1] = 1;
// 从2个节点开始计算
for (int i = 2; i <= n; i++) {
// j为左子树节点数, 由于根节点需要占一个位置, 所以j的取值范围是0到i-1
for (int j = 0; j < i; j++)
// 计算组合数, 累计不同的根节点情况下, 所有左右子树的组合数
dp[i] += dp[j] * dp[i - j - 1];
}
System.out.println(JSON.toJSONString(dp));
}这个题目的关键点就是思路的切换。
总结
每天进步一点点！