上海
专栏：50多种数据结构彻底征服
专栏：50多种经典图论算法全部掌握
最近一网友在网上发文称pdd的校招礼物是2025春节祝福表情包，该网友绷不住了，还引起其他网友的热议，有的网友称之前还发了电子台历，还有的发了校招壁纸。我离校招都十多年了，不记得当时是否有校招礼物，现在都流行发这个吗？
--------------下面是今天的算法题--------------
来看下今天的算法题，这题是LeetCode的第96题：不同的二叉搜索树。
问题描述
来源：LeetCode第96题
难度：中等
给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的二叉搜索树 有多少种？返回满足题意的 二叉搜索树 的种数。
示例1：
输入：n = 3 输出：5
示例2：
输入：n = 1 输出：1
1 <= n <= 19
问题分析
这题让计算 n 个节点可以构成多个二叉搜索树。我们可以这样来思考，二叉树肯定有根节点，去掉根节点之后还有 n-1 个子节点。在这 n-1 个子节点中，左子节点可以有 0 个，也可以有 1 个，也可以有 2 个……
如果左子节点是 j 个，那么右子节点就是 n-1-j 个，它们构成的二叉搜索树就是左子树构成的个数乘以右子树构成的个数，所以这是一个动态规划问题。
定义dp[i]表示 i 个节点构成的二叉搜索树个数，当 i 等于 1 的时候只有一种情况。当左子节点个数为 0 的时候，构成的二叉搜索树就是右子节点构成的个数，所以我们这里让dp[0]也等于 1 。
当计算 i 个节点的时候，我们只需要枚举左子树的个数从 0 到 i-1 即可，代码如下：
JAVA：
public int numTrees(int n) { int dp[] = new int[n + 1]; dp[0] = dp[1] = 1;// 节点为0和1的时候，只有一种。 for (int i = 2; i <= n; i++) for (int j = 0; j < i; j++) // j是左子节点个数，i-j-1是右子节点个数。 dp[i] += dp[j] * dp[i - j - 1]; return dp[n]; }C++：
public: int numTrees(int n) { vector
dp(n + 1); dp[0] = dp[1] = 1;// 节点为0和1的时候，只有一种。 for (int i = 2; i <= n; i++) for (int j = 0; j < i; j++) // j是左子节点个数，i-j-1是右子节点个数。 dp[i] += dp[j] * dp[i - j - 1]; return dp[n]; }
Python：
def numTrees(self, n: int) -> int: dp = [0] * (n + 1) dp[0] = dp[1] = 1 # 节点为0和1的时候，只有一种。 for i in range(2, n + 1): for j in range(i): # j是左子节点个数，i-j-1是右子节点个数。 dp[i] += dp[j] * dp[i - j - 1] return dp[n]笔者简介
博哥，真名：王一博，毕业十多年， 作者，专注于 数据结构和算法 的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解800多题，对算法题有自己独特的解题思路和解题技巧，喜欢的可以给个关注，也可以 下载我整理的1000多页的PDF算法文档 。
特别声明：以上内容(如有图片或视频亦包括在内)为自媒体平台“网易号”用户上传并发布，本平台仅提供信息存储服务。
Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.
