6230 字
约 20 分钟
11
096.不同的二叉搜索树
2026-09-19
数据结构与算法
无标签

096.不同的二叉搜索树

作者：沉默王二
发布时间：2023-11-04T16:46:43.700+0800

本题解同时收录在星球专栏《二哥的 LeetCode 刷题笔记》中，专栏托管在语雀平台上（更方便你沉浸式阅读和做笔记），访问地址和密码：https://t.zsxq.com/6iuzn6I

题意

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

难度

中等

示例

示例 1：

输入：n=3

示例 2：

输入：n=1

分析

关于**二叉搜索树 **，上一题我们就讲过了，相信大家还有印象。上一题是求具体方案，这一题是求方案的个数。

我们可以沿用上一题的思路。

假设n个节点的 二叉搜索树 的个数为 G(n)，设 f(i) 为以为根节点的、大小为n的二叉搜索树的个数。

则我们可以得到以下式子：

并且当我们分析的时候，还可以得到这样一个式子：

因为我们知道，总数为n的话，当前节点的两个子树，必然是大小为i-1和n-i的两棵小的二叉搜索树。

综合一下两个公式我们就能得到：

而这，就是我们**上一题 **提到的 卡特兰数，有印象吧？

按照上述公式我们就可以写出这么一个题解：

classSolution{

publicintnumTrees(intn){//如果n为0，按照定义，空树也是一种有效的二叉搜索树。if(n==0){return1;}//初始化结果变量res，用于累加所有可能的二叉搜索树的数量。intres=0;//遍历每个数字i，将其作为根节点，以计算所有可能的二叉搜索树。for(inti=1;i<=n;i++){//递归计算左子树的数量，左子树包含比根节点小的i-1个节点。intleft=numTrees(i-1);//递归计算右子树的数量，右子树包含比根节点大的n-i个节点。intright=numTrees(n-i);//将左子树和右子树的组合数量相乘，并加到总数res上。//这是基于卡特兰数的数学性质，每个左子树都可以与任何一个右子树组合形成唯一的二叉搜索树。res+=left*right;}//返回计算得出的二叉搜索树的总数量。returnres;}}

很遗憾，虽然能正确的计算出答案，但它的效率实在太低了，并不能通过所有的测试点，n=18 的时候超出了时间限制。

因为它多次重复计算相同的子问题（即存在大量的重复计算），这使得其时间复杂度指数级增加。

所以我们来改进一下：将已经计算过的numTrees(i)保存下来。

classSolution{

publicint[]nums=newint[20];
//主方法，计算并返回n个节点组成的唯一二叉搜索树的数量publicintnumTrees(intn){//基本情况：如果n是0，则有一个空的二叉树if(n==0){return1;}//如果之前已经计算过这个结果，直接返回缓存中的值if(nums[n]!=0){returnnums[n];}
//初始化结果变量resintres=0;//遍历每个数字i，考虑将其作为根节点for(inti=1;i<=n;i++){//尝试从缓存中获取左子树的数量intleft=nums[i-1];//如果缓存中没有，则递归计算并更新缓存if(left==0){nums[i-1]=numTrees(i-1);left=nums[i-1];}//尝试从缓存中获取右子树的数量intright=nums[n-i];//如果缓存中没有，则递归计算并更新缓存if(right==0){nums[n-i]=numTrees(n-i);right=nums[n-i];}//累加左子树和右子树的组合数量res+=left*right;}//缓存这个结果，以便将来可以重用nums[n]=res;//返回计算得出的二叉搜索树的总数量returnres;}}

由于题目描述中，明确给出了提示 1 <= n <= 19，所以我们定义数组 nums 来存储每个数 n 对应的结果，避免重复计算相同的子问题。

递归会先查看缓存，如果结果不在缓存中，则进行计算并更新缓存，所以效率提高了很多。

能看得出来，我们采用了“空间换时间”的策略，使得我们的速度变快了不少。我们可以通过一个具体的例子来说明这个优化的点。

假设我们要计算 numTrees(4)，也就是由 4 个节点能组成的唯一二叉搜索树的数量。不使用记忆化的递归会进行很多重复计算，因为递归树中会有重叠的子问题。这里是不使用记忆化时的递归调用树的一个示例：

numTrees(4)

│└──numTrees(3)//这里开始重复计算numTrees(3)│├──numTrees(0)*numTrees(2)//i=1││└──numTrees(2)//再次重复计算numTrees(2)│├──numTrees(1)*numTrees(1)//i=2│└──numTrees(2)*numTrees(0)//i=3│└──numTrees(2)//再次重复计算numTrees(2)├──numTrees(1)*numTrees(2)//i=2,根为2，左子树有1个节点├──numTrees(2)*numTrees(1)//i=3,根为3，右子树有1个节点└──numTrees(3)*numTrees(0)//i=4,根为4，右子树为空└──numTrees(3)//再次重复计算numTrees(3)

在上面的示例中，numTrees(3) 和 numTrees(2) 被计算了多次。

现在，让我们看看加入记忆化后的优化效果：

numTrees(4)

│└──numTrees(3)//计算numTrees(3)，结果存入缓存│├──numTrees(0)*numTrees(2)//i=1││└──numTrees(2)//计算numTrees(2)，结果存入缓存│├──numTrees(1)*numTrees(1)//i=2│└──numTrees(2)*numTrees(0)//i=3│└──numTrees(2)//直接从缓存读取结果，不再重新计算├──numTrees(1)*numTrees(2)//i=2,根为2，左子树有1个节点├──numTrees(2)*numTrees(1)//i=3,根为3，右子树有1个节点│└──numTrees(2)//直接从缓存读取结果，不再重新计算└──numTrees(3)*numTrees(0)//i=4,根为4，右子树为空└──numTrees(3)//直接从缓存读取结果，不再重新计算

在优化的版本中，我们看到 numTrees(2) 和 numTrees(3) 只计算了一次。它们的结果被存入 nums 数组。后续的递归调用不再执行计算，而是直接从 nums 数组中读取结果。

这样的优化显著减少了递归调用的次数，因此减少了计算量，提高了效率。

不过，我们还能进一步优化，还记得之前说过的 卡特兰数 吗？

通过前人的经验，可以得到卡特兰数的递推公式：

这样子我们就可以既快速又方便地解开这道题：

classSolution{

//使用long类型来存储中间结果，防止溢出longres=1;//遍历从0到n-1for(inti=0;i<n;++i){//使用卡特兰数的计算公式//这里我们使用的是：C(n+1)=2(2n+1)/(n+2)C(n)res=res2*(2*i+1)/(i+2);}//将结果转换为int类型返回//因为最终结果是确定可以被int表示的，所以这里的类型转换是安全的return(int)res;}}

它利用了这样一个事实：Ci+1可以直接通过 Ci 计算得到，无需从头开始计算。因此，这种方法只需要线性时间就可以完成计算，非常高效。

卡特兰数 Cn可以用以下递归关系来表示：

现在，如果要计算 C3，过程应该是这样的：

对于，存在 5 种唯一的二叉搜索树的构造方式。

我们把优化后的递归改成 ACM 输入输出的模式，通过控制台来打印一下结果。

importjava.util.Scanner;

publicclassUniqueBinarySearchTrees{
//使用一个数组来存储已经计算过的结果privatestaticint[]cache;
publicstaticvoidmain(String[]args){Scannerscanner=newScanner(System.in);System.out.print("键入n的大小:");intn=scanner.nextInt();
//初始化记忆数组，大小为n+1，所有值默认为0cache=newint[n+1];
//计算并打印结果System.out.println("二叉搜索树的数量n="+n+"是:"+numTrees(n));}
publicstaticintnumTrees(intn){if(n<=1){return1;}if(cache[n]!=0){returncache[n];}
intsum=0;for(inti=1;i<=n;i++){sum+=numTrees(i-1)*numTrees(n-i);}
cache[n]=sum;returnsum;}}

我们来验证一下，当 n 为 4 的时候，结果是 14，通过卡特兰数的解题方法可以验证一下，因 n 为 3 的时候结果是 5。

总结

我们通过总结二叉搜索树的数量，一步一步改进我们的算法，最后使用了卡特兰数的递推公式得到较好的结果。

力扣链接：https://leetcode.cn/problems/unique-binary-search-trees/

一步一个脚印

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。

PDF 版本目前只针对**二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 **加入我们吧。

一个人可以走得很快，但一群人才能走得更远。二哥编程星球 （目前已有 3800 多名球友加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！

本题解同时收录在星球专栏《二哥的 LeetCode 刷题笔记》中，专栏托管在语雀平台上（更方便你沉浸式阅读和做笔记），访问地址和密码：https://t.zsxq.com/6iuzn6I

题意

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

难度

中等

示例

示例 1：

输入：n=3

示例 2：

输入：n=1

分析

关于**二叉搜索树 **，上一题我们就讲过了，相信大家还有印象。上一题是求具体方案，这一题是求方案的个数。

我们可以沿用上一题的思路。

假设n个节点的 二叉搜索树 的个数为 G(n)，设 f(i) 为以为根节点的、大小为n的二叉搜索树的个数。

则我们可以得到以下式子：

并且当我们分析的时候，还可以得到这样一个式子：

因为我们知道，总数为n的话，当前节点的两个子树，必然是大小为i-1和n-i的两棵小的二叉搜索树。

综合一下两个公式我们就能得到：

而这，就是我们**上一题 **提到的 卡特兰数，有印象吧？

按照上述公式我们就可以写出这么一个题解：

classSolution{

publicintnumTrees(intn){//如果n为0，按照定义，空树也是一种有效的二叉搜索树。if(n==0){return1;}//初始化结果变量res，用于累加所有可能的二叉搜索树的数量。intres=0;//遍历每个数字i，将其作为根节点，以计算所有可能的二叉搜索树。for(inti=1;i<=n;i++){//递归计算左子树的数量，左子树包含比根节点小的i-1个节点。intleft=numTrees(i-1);//递归计算右子树的数量，右子树包含比根节点大的n-i个节点。intright=numTrees(n-i);//将左子树和右子树的组合数量相乘，并加到总数res上。//这是基于卡特兰数的数学性质，每个左子树都可以与任何一个右子树组合形成唯一的二叉搜索树。res+=left*right;}//返回计算得出的二叉搜索树的总数量。returnres;}}

很遗憾，虽然能正确的计算出答案，但它的效率实在太低了，并不能通过所有的测试点，n=18 的时候超出了时间限制。

因为它多次重复计算相同的子问题（即存在大量的重复计算），这使得其时间复杂度指数级增加。

所以我们来改进一下：将已经计算过的numTrees(i)保存下来。

classSolution{

publicint[]nums=newint[20];
//主方法，计算并返回n个节点组成的唯一二叉搜索树的数量publicintnumTrees(intn){//基本情况：如果n是0，则有一个空的二叉树if(n==0){return1;}//如果之前已经计算过这个结果，直接返回缓存中的值if(nums[n]!=0){returnnums[n];}
//初始化结果变量resintres=0;//遍历每个数字i，考虑将其作为根节点for(inti=1;i<=n;i++){//尝试从缓存中获取左子树的数量intleft=nums[i-1];//如果缓存中没有，则递归计算并更新缓存if(left==0){nums[i-1]=numTrees(i-1);left=nums[i-1];}//尝试从缓存中获取右子树的数量intright=nums[n-i];//如果缓存中没有，则递归计算并更新缓存if(right==0){nums[n-i]=numTrees(n-i);right=nums[n-i];}//累加左子树和右子树的组合数量res+=left*right;}//缓存这个结果，以便将来可以重用nums[n]=res;//返回计算得出的二叉搜索树的总数量returnres;}}

由于题目描述中，明确给出了提示 1 <= n <= 19，所以我们定义数组 nums 来存储每个数 n 对应的结果，避免重复计算相同的子问题。

递归会先查看缓存，如果结果不在缓存中，则进行计算并更新缓存，所以效率提高了很多。

能看得出来，我们采用了“空间换时间”的策略，使得我们的速度变快了不少。我们可以通过一个具体的例子来说明这个优化的点。

假设我们要计算 numTrees(4)，也就是由 4 个节点能组成的唯一二叉搜索树的数量。不使用记忆化的递归会进行很多重复计算，因为递归树中会有重叠的子问题。这里是不使用记忆化时的递归调用树的一个示例：

numTrees(4)

│└──numTrees(3)//这里开始重复计算numTrees(3)│├──numTrees(0)*numTrees(2)//i=1││└──numTrees(2)//再次重复计算numTrees(2)│├──numTrees(1)*numTrees(1)//i=2│└──numTrees(2)*numTrees(0)//i=3│└──numTrees(2)//再次重复计算numTrees(2)├──numTrees(1)*numTrees(2)//i=2,根为2，左子树有1个节点├──numTrees(2)*numTrees(1)//i=3,根为3，右子树有1个节点└──numTrees(3)*numTrees(0)//i=4,根为4，右子树为空└──numTrees(3)//再次重复计算numTrees(3)

在上面的示例中，numTrees(3) 和 numTrees(2) 被计算了多次。

现在，让我们看看加入记忆化后的优化效果：

numTrees(4)

│└──numTrees(3)//计算numTrees(3)，结果存入缓存│├──numTrees(0)*numTrees(2)//i=1││└──numTrees(2)//计算numTrees(2)，结果存入缓存│├──numTrees(1)*numTrees(1)//i=2│└──numTrees(2)*numTrees(0)//i=3│└──numTrees(2)//直接从缓存读取结果，不再重新计算├──numTrees(1)*numTrees(2)//i=2,根为2，左子树有1个节点├──numTrees(2)*numTrees(1)//i=3,根为3，右子树有1个节点│└──numTrees(2)//直接从缓存读取结果，不再重新计算└──numTrees(3)*numTrees(0)//i=4,根为4，右子树为空└──numTrees(3)//直接从缓存读取结果，不再重新计算

在优化的版本中，我们看到 numTrees(2) 和 numTrees(3) 只计算了一次。它们的结果被存入 nums 数组。后续的递归调用不再执行计算，而是直接从 nums 数组中读取结果。

这样的优化显著减少了递归调用的次数，因此减少了计算量，提高了效率。

不过，我们还能进一步优化，还记得之前说过的 卡特兰数 吗？

通过前人的经验，可以得到卡特兰数的递推公式：

这样子我们就可以既快速又方便地解开这道题：

classSolution{

//使用long类型来存储中间结果，防止溢出longres=1;//遍历从0到n-1for(inti=0;i<n;++i){//使用卡特兰数的计算公式//这里我们使用的是：C(n+1)=2(2n+1)/(n+2)C(n)res=res2*(2*i+1)/(i+2);}//将结果转换为int类型返回//因为最终结果是确定可以被int表示的，所以这里的类型转换是安全的return(int)res;}}

它利用了这样一个事实：Ci+1可以直接通过 Ci 计算得到，无需从头开始计算。因此，这种方法只需要线性时间就可以完成计算，非常高效。

卡特兰数 Cn可以用以下递归关系来表示：

现在，如果要计算 C3，过程应该是这样的：

对于，存在 5 种唯一的二叉搜索树的构造方式。

我们把优化后的递归改成 ACM 输入输出的模式，通过控制台来打印一下结果。

importjava.util.Scanner;

publicclassUniqueBinarySearchTrees{
//使用一个数组来存储已经计算过的结果privatestaticint[]cache;
publicstaticvoidmain(String[]args){Scannerscanner=newScanner(System.in);System.out.print("键入n的大小:");intn=scanner.nextInt();
//初始化记忆数组，大小为n+1，所有值默认为0cache=newint[n+1];
//计算并打印结果System.out.println("二叉搜索树的数量n="+n+"是:"+numTrees(n));}
publicstaticintnumTrees(intn){if(n<=1){return1;}if(cache[n]!=0){returncache[n];}
intsum=0;for(inti=1;i<=n;i++){sum+=numTrees(i-1)*numTrees(n-i);}
cache[n]=sum;returnsum;}}

我们来验证一下，当 n 为 4 的时候，结果是 14，通过卡特兰数的解题方法可以验证一下，因 n 为 3 的时候结果是 5。

总结

我们通过总结二叉搜索树的数量，一步一步改进我们的算法，最后使用了卡特兰数的递推公式得到较好的结果。

力扣链接：https://leetcode.cn/problems/unique-binary-search-trees/

一步一个脚印

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。

PDF 版本目前只针对**二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 **加入我们吧。

一个人可以走得很快，但一群人才能走得更远。二哥编程星球 （目前已有 3800 多名球友加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！

本题解同时收录在星球专栏《二哥的 LeetCode 刷题笔记》中，专栏托管在语雀平台上（更方便你沉浸式阅读和做笔记），访问地址和密码：https://t.zsxq.com/6iuzn6I

题意

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

难度

中等

示例

示例 1：

输入：n=3

示例 2：

输入：n=1

分析

关于**二叉搜索树 **，上一题我们就讲过了，相信大家还有印象。上一题是求具体方案，这一题是求方案的个数。

我们可以沿用上一题的思路。

假设n个节点的 二叉搜索树 的个数为 G(n)，设 f(i) 为以为根节点的、大小为n的二叉搜索树的个数。

则我们可以得到以下式子：

并且当我们分析的时候，还可以得到这样一个式子：

因为我们知道，总数为n的话，当前节点的两个子树，必然是大小为i-1和n-i的两棵小的二叉搜索树。

综合一下两个公式我们就能得到：

而这，就是我们**上一题 **提到的 卡特兰数，有印象吧？

按照上述公式我们就可以写出这么一个题解：

classSolution{

publicintnumTrees(intn){//如果n为0，按照定义，空树也是一种有效的二叉搜索树。if(n==0){return1;}//初始化结果变量res，用于累加所有可能的二叉搜索树的数量。intres=0;//遍历每个数字i，将其作为根节点，以计算所有可能的二叉搜索树。for(inti=1;i<=n;i++){//递归计算左子树的数量，左子树包含比根节点小的i-1个节点。intleft=numTrees(i-1);//递归计算右子树的数量，右子树包含比根节点大的n-i个节点。intright=numTrees(n-i);//将左子树和右子树的组合数量相乘，并加到总数res上。//这是基于卡特兰数的数学性质，每个左子树都可以与任何一个右子树组合形成唯一的二叉搜索树。res+=left*right;}//返回计算得出的二叉搜索树的总数量。returnres;}}

很遗憾，虽然能正确的计算出答案，但它的效率实在太低了，并不能通过所有的测试点，n=18 的时候超出了时间限制。

因为它多次重复计算相同的子问题（即存在大量的重复计算），这使得其时间复杂度指数级增加。

所以我们来改进一下：将已经计算过的numTrees(i)保存下来。

classSolution{

publicint[]nums=newint[20];
//主方法，计算并返回n个节点组成的唯一二叉搜索树的数量publicintnumTrees(intn){//基本情况：如果n是0，则有一个空的二叉树if(n==0){return1;}//如果之前已经计算过这个结果，直接返回缓存中的值if(nums[n]!=0){returnnums[n];}
//初始化结果变量resintres=0;//遍历每个数字i，考虑将其作为根节点for(inti=1;i<=n;i++){//尝试从缓存中获取左子树的数量intleft=nums[i-1];//如果缓存中没有，则递归计算并更新缓存if(left==0){nums[i-1]=numTrees(i-1);left=nums[i-1];}//尝试从缓存中获取右子树的数量intright=nums[n-i];//如果缓存中没有，则递归计算并更新缓存if(right==0){nums[n-i]=numTrees(n-i);right=nums[n-i];}//累加左子树和右子树的组合数量res+=left*right;}//缓存这个结果，以便将来可以重用nums[n]=res;//返回计算得出的二叉搜索树的总数量returnres;}}

由于题目描述中，明确给出了提示 1 <= n <= 19，所以我们定义数组 nums 来存储每个数 n 对应的结果，避免重复计算相同的子问题。

递归会先查看缓存，如果结果不在缓存中，则进行计算并更新缓存，所以效率提高了很多。

能看得出来，我们采用了“空间换时间”的策略，使得我们的速度变快了不少。我们可以通过一个具体的例子来说明这个优化的点。

假设我们要计算 numTrees(4)，也就是由 4 个节点能组成的唯一二叉搜索树的数量。不使用记忆化的递归会进行很多重复计算，因为递归树中会有重叠的子问题。这里是不使用记忆化时的递归调用树的一个示例：

numTrees(4)

│└──numTrees(3)//这里开始重复计算numTrees(3)│├──numTrees(0)*numTrees(2)//i=1││└──numTrees(2)//再次重复计算numTrees(2)│├──numTrees(1)*numTrees(1)//i=2│└──numTrees(2)*numTrees(0)//i=3│└──numTrees(2)//再次重复计算numTrees(2)├──numTrees(1)*numTrees(2)//i=2,根为2，左子树有1个节点├──numTrees(2)*numTrees(1)//i=3,根为3，右子树有1个节点└──numTrees(3)*numTrees(0)//i=4,根为4，右子树为空└──numTrees(3)//再次重复计算numTrees(3)

在上面的示例中，numTrees(3) 和 numTrees(2) 被计算了多次。

现在，让我们看看加入记忆化后的优化效果：

numTrees(4)

│└──numTrees(3)//计算numTrees(3)，结果存入缓存│├──numTrees(0)*numTrees(2)//i=1││└──numTrees(2)//计算numTrees(2)，结果存入缓存│├──numTrees(1)*numTrees(1)//i=2│└──numTrees(2)*numTrees(0)//i=3│└──numTrees(2)//直接从缓存读取结果，不再重新计算├──numTrees(1)*numTrees(2)//i=2,根为2，左子树有1个节点├──numTrees(2)*numTrees(1)//i=3,根为3，右子树有1个节点│└──numTrees(2)//直接从缓存读取结果，不再重新计算└──numTrees(3)*numTrees(0)//i=4,根为4，右子树为空└──numTrees(3)//直接从缓存读取结果，不再重新计算

在优化的版本中，我们看到 numTrees(2) 和 numTrees(3) 只计算了一次。它们的结果被存入 nums 数组。后续的递归调用不再执行计算，而是直接从 nums 数组中读取结果。

这样的优化显著减少了递归调用的次数，因此减少了计算量，提高了效率。

不过，我们还能进一步优化，还记得之前说过的 卡特兰数 吗？

通过前人的经验，可以得到卡特兰数的递推公式：

这样子我们就可以既快速又方便地解开这道题：

classSolution{

//使用long类型来存储中间结果，防止溢出longres=1;//遍历从0到n-1for(inti=0;i<n;++i){//使用卡特兰数的计算公式//这里我们使用的是：C(n+1)=2(2n+1)/(n+2)C(n)res=res2*(2*i+1)/(i+2);}//将结果转换为int类型返回//因为最终结果是确定可以被int表示的，所以这里的类型转换是安全的return(int)res;}}

它利用了这样一个事实：Ci+1可以直接通过 Ci 计算得到，无需从头开始计算。因此，这种方法只需要线性时间就可以完成计算，非常高效。

卡特兰数 Cn可以用以下递归关系来表示：

现在，如果要计算 C3，过程应该是这样的：

对于，存在 5 种唯一的二叉搜索树的构造方式。

我们把优化后的递归改成 ACM 输入输出的模式，通过控制台来打印一下结果。

importjava.util.Scanner;

publicclassUniqueBinarySearchTrees{
//使用一个数组来存储已经计算过的结果privatestaticint[]cache;
publicstaticvoidmain(String[]args){Scannerscanner=newScanner(System.in);System.out.print("键入n的大小:");intn=scanner.nextInt();
//初始化记忆数组，大小为n+1，所有值默认为0cache=newint[n+1];
//计算并打印结果System.out.println("二叉搜索树的数量n="+n+"是:"+numTrees(n));}
publicstaticintnumTrees(intn){if(n<=1){return1;}if(cache[n]!=0){returncache[n];}
intsum=0;for(inti=1;i<=n;i++){sum+=numTrees(i-1)*numTrees(n-i);}
cache[n]=sum;returnsum;}}

我们来验证一下，当 n 为 4 的时候，结果是 14，通过卡特兰数的解题方法可以验证一下，因 n 为 3 的时候结果是 5。

总结

我们通过总结二叉搜索树的数量，一步一步改进我们的算法，最后使用了卡特兰数的递推公式得到较好的结果。

力扣链接：https://leetcode.cn/problems/unique-binary-search-trees/

一步一个脚印

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。

PDF 版本目前只针对**二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 **加入我们吧。

一个人可以走得很快，但一群人才能走得更远。二哥编程星球 （目前已有 3800 多名球友加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！

            知识星球
            
    
    
        
        扫码加入星球
        查看更多优质内容
    
    https://wx.zsxq.com/mweb/views/joingroup/join_group.html?group_id=15522885221412
096.不同的二叉搜索树
https://clxhxhhr.top/posts/2550/
作者
clxstart
发布于
2026-09-19
许可协议
CC BY-NC-SA 4.0
095.不同的二叉搜索树 II
097.交错字符串
评论
0 条
还没有评论，先写一条吧。