0096. 不同的二叉搜索树
大约 2 分钟
--- 
0096. 不同的二叉搜索树
- 标签:树、二叉搜索树、数学、动态规划、二叉树
- 难度:中等
题目链接
题目大意
描述:给定一个整数 。
要求:求以 到 为节点构成的「二叉搜索树」有多少种?
说明:
- 。
示例:
- 示例 1:

输入:n = 3
输出:5
- 示例 2:
输入:n = 1
输出:1
解题思路
思路 1:动态规划
一棵搜索二叉树的左、右子树,要么也是搜索二叉树,要么就是空树。
如果定义 表示以 为根的二叉搜索树个数,定义 表示 个节点可以构成的二叉搜索树个数,则有:
- 。
其中当 为根节点时,则用 共 个节点去递归构建左子搜索二叉树,用 共 个节点去递归构建右子搜索树。则有:
- 。
综合上面两个式子 可得出:
- 。
将 换为 ,可变为:
- 。
再转换一下,可变为:
- 。
则我们可以通过动态规划的方法,递推求解 ,并求解出 。具体步骤如下:
1. 划分阶段
按照根节点的编号进行阶段划分。
2. 定义状态
定义状态 表示为: 个节点可以构成的二叉搜索树个数。
3. 状态转移方程
4. 初始条件
- 个节点可以构成的二叉搜索树个数为 (空树),即 。
5. 最终结果
根据我们之前定义的状态, 表示为: 个节点可以构成的二叉搜索树个数。。 所以最终结果为 。
思路 1:代码
class Solution:
def numTrees(self, n: int) -> int:
dp = [0 for _ in range(n + 1)]
dp[0] = 1
for i in range(1, n + 1):
for j in range(1, i + 1):
dp[i] += dp[j - 1] * dp[i - j]
return dp[n]
思路 1:复杂度分析
- 时间复杂度:。
- 空间复杂度:。