专栏：50多种数据结构彻底征服
专栏：50多种经典图论算法全部掌握
世界之大，无奇不有，最近一C++网友在找工作的时候，HR给他开出了高达50元的日薪，该网友感觉受到了侮辱。还好，评论区另一网友实在看不下去，替他给骂了回去。
网友评论：
--------------下面是今天的算法题--------------
来看下今天的算法题，这题是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算法文档 。
热门跟贴