作者介绍：10年大厂数据\经营分析经验，现任大厂数据部门负责人。
会一些的技术：数据分析、算法、SQL、大数据相关、python
欢迎加入社区：码上找工作
作者专栏每日更新：
备注说明：方便大家阅读，统一使用python，带必要注释，公众号 数据分析螺丝钉 一起打怪升级
题目描述
给定一个整数 n，求以 1 到 n 为节点组成的二叉搜索树 (BST) 有多少种不同的形状。
输入格式
- n：整数，表示节点的数目。
输出格式
- 返回不同的 BST 的数目。
示例
示例 1
输入: n = 3 输出: 5 解释: 给定 n = 3, 有五种不同形状的 BST: 1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 2 / / \ \ 2 1 2 3
方法一：动态规划
解题步骤
- 定义状态：
dp[i]表示由i个节点能构成的不同 BST 的数目。 - 状态转移：
dp[i]由所有可能的左右子树的组合数之和决定。即dp[i] = ∑(dp[j-1] * dp[i-j])，其中j表示根节点的位置。
完整的规范代码
def numTrees(n): """ 使用动态规划计算不同的二叉搜索树的数量 :param n: int, 节点的数目 :return: int, 不同的 BST 数量 """ dp = [0] * (n + 1) dp[0], dp[1] = 1, 1 for i in range(2, n + 1): for j in range(1, i + 1): dp[i] += dp[j - 1] * dp[i - j] return dp[n] # 示例调用 print(numTrees(3)) # 输出: 5
算法分析
- 时间复杂度：(O(n^2))，由于双层循环的存在。
- 空间复杂度：(O(n))，用于存储中间结果的数组。
算法图解
为了提供一个更直观的视觉展示来理解问题 96 “不同的二叉搜索树” 使用动态规划方法的计算过程，我们可以尝试通过一个更细节的 ASCII 图形来表达 dp 数组的更新流程，这会帮助我们直观地看到每一步的计算和累加过程。
假设我们计算 n = 4 时的情况，我们详细列出每一步的计算，展示根节点选择不同的情况如何贡献到 dp 数组的计算中。
ASCII 表的直观表示
这里是一个逐步展开的表格，用于计算不同的二叉搜索树数量，其中 | 表示不同的根节点选择对应的贡献。
dp[0] = 1 (空树) dp[1] = 1 (单节点树) Calculating dp[2]: Root 1: dp[0] * dp[1] = 1 * 1 = 1 | 1 Root 2: dp[1] * dp[0] = 1 * 1 = 1 | 1 dp[2] = 1 + 1 = 2 Calculating dp[3]: Root 1: dp[0] * dp[2] = 1 * 2 = 2 | 2 Root 2: dp[1] * dp[1] = 1 * 1 = 1 | 1 Root 3: dp[2] * dp[0] = 2 * 1 = 2 | 2 dp[3] = 2 + 1 + 2 = 5 Calculating dp[4]: Root 1: dp[0] * dp[3] = 1 * 5 = 5 | 5 Root 2: dp[1] * dp[2] = 1 * 2 = 2 | 2 Root 3: dp[2] * dp[1] = 2 * 1 = 2 | 2 Root 4: dp[3] * dp[0] = 5 * 1 = 5 | 5 dp[4] = 5 + 2 + 2 + 5 = 14
可视化解释
- 每一行表示计算一个
dp[i]的过程。 |之后的数字表示该根节点下左右子树组合的贡献。- 每个
Root x:开头的部分表示选择x作为根节点时，左右子树组成部分的贡献。
这种方式的展示将每个步骤拆分开来，明确每个选择的贡献如何累加到最终结果中，从而帮助读者更好地理解动态规划表是如何一步步构建起来的，特别是如何通过结合前面计算的结果来解决当前问题的。希望这种方法能够更直观地展示动态规划的计算过程。
方法二：递归（带记忆化）
解题步骤
- 递归定义：利用递归直接根据
dp的定义进行计算，对于每个i计算1到i的根节点所能形成的 BST 数量。 - 记忆化：使用哈希表存储已计算的结果，避免重复计算。
完整的规范代码
def numTrees(n): memo = {} def countTrees(n): if n in memo: return memo[n] if n <= 1: return 1 total = 0 for i in range(1, n + 1): left = countTrees(i - 1) right = countTrees(n - i) total += left * right memo[n] = total return total return countTrees(n) # 示例调用 print(numTrees(3)) # 输出: 5
算法分析
- 时间复杂度：(O(n^2))，尽管有递归调用，但由于记忆化的存在，每个子问题只解决一次。
- 空间复杂度：(O(n))，用于存储记忆化结果的哈希表。
方法三：数学公式 - 卡塔兰数
解题步骤
完整的规范代码
def numTrees(n): """ 使用卡塔兰数公式计算不同的二叉搜索树的数量 :param n: int, 节点的数目 :return: int, 不同的 BST 数量 """ import math return math.comb(2 * n, n) // (n + 1) # 示例调用 print(numTrees(3)) # 输出: 5
算法分析
- 时间复杂度：(O(n))，主要消耗在计算组合数上。
- 空间复杂度：(O(1))，不需要额外的存储空间。
不同算法的优劣势对比
| 特征 | 方法一：动态规划 | 方法二：递归（带记忆化） | 方法三：卡塔兰数 |
| 时间复杂度 | (O(n^2)) | (O(n^2)) | (O(n)) |
| 空间复杂度 | (O(n)) | (O(n)) | (O(1)) |
| 优势 | 结构清晰、易于实现 | 避免重复计算、提高效率 | 计算最快、不需要额外空间 |
| 劣势 | 计算时间较长 | 空间复杂度较高，较复杂 | 需要理解卡塔兰数背后的数学原理 |
应用示例
这些方法可以用于算法设计与数据结构教学中，展示不同的动态规划技术和数学应用。它们也适用于任何需要预测或计算不同结构可能性的领域，如计算生物学、化学结构分析等领域。
欢迎关注微信公众号 数据分析螺丝钉
