🌈🌈😄😄
欢迎来到茶色岛独家岛屿，本期将为大家揭晓LeetCode 96. 不同的二叉搜索树 ，做好准备了么，那么开始吧。
🌲🌲🐴🐴
一、题目名称
LeetCode 96. 不同的二叉搜索树
二、题目要求
给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
三、相应举例
示例 1：
输入：n = 3
输出：5
示例 2：
输入：n = 1
输出：1
四、限制要求
- *
1 <= n <="8</code"><!--=-->
五、解决办法
动态规划
题目要求是计算不同二叉搜索树的个数。为此，我们可以定义两个函数：
G(n): 长度为 n 的序列能构成的不同二叉搜索树的个数。
F(i, n): 以 i为根、序列长度为 n 的不同二叉搜索树个数 (1≤i≤n)。
可见，G(n) 是我们求解需要的函数。
稍后我们将看到，G(n) 可以从 F(i,n) 得到，而F(i,n) 又会递归地依赖于 G(n)。
对于边界情况，当序列长度为 1（只有根）或为 0（空树）时，只有一种情况，即：
G(0)=1,G(1)=1
六、代码实现
方法一：动态规划
class Solution {
public int numTrees(int n) {
int[] G = new int[n + 1];
G[0] = 1;
G[1] = 1;
for (int i = 2; i
外层for循环是遍历G中从2开始到n的每个节点，目的是为了求出类似于G（2），G（3）等等，若直接使用下面的循环，如下图：
刚开始会出现G（2）=0，求出G（n）=0的现象，而
使用外层循环可以依次求出G（2），G（3）等，即节点的 二叉搜索树的种数，可以防止这种情况出现。如下图：
每次循环可依次求出G（2），G（3）等 二叉搜索树的种数，直到最后求G（n）。
方法二：递归
Map map = new HashMap<>();
public int numTrees(int n) {
if (n == 0 || n == 1){
return 1;
}
//防止重复递归查找
if (map.containsKey(n)){
return map.get(n);
}
int count = 0;
//当i为根节点时
for (int i = 1; i
Original: https://blog.csdn.net/weixin_62275996/article/details/128707939
Author: 茶色岛
Title: LeetCode 96. 不同的二叉搜索树
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/815084/
转载文章受原作者版权保护。转载请注明原作者出处！