作者介绍：10年大厂数据\经营分析经验，现任大厂数据部门负责人。
会一些的技术：数据分析、算法、SQL、大数据相关、python
欢迎加入社区：码上找工作
作者专栏每日更新：
备注说明：方便大家阅读，统一使用python，带必要注释，公众号 数据分析螺丝钉 一起打怪升级
本文探讨了多种生成所有可能二叉搜索树的算法，包括递归分治法、动态规划、记忆化递归，详解每种方法的实现及优劣势。
题目描述
给定一个整数 n，生成所有由 1 到 n 为节点所组成的二叉搜索树 (BST)。
输入格式
- n：表示生成树的节点值的上限。
输出格式
- 返回所有存储结构为
TreeNode的 BST 的列表。
示例
示例 1
输入: n = 3 输出: [ [1,null,3,2], [3,2,null,1], [3,1,null,null,2], [2,1,3], [1,null,2,null,3] ]
解释：输出的数组表示 5 种不同结构的 BST 的根节点。
方法一：递归分治法
解题步骤
- 分治策略：对于每个数
i，使其为根节点，然后递归地生成所有可能的左子树和右子树。 - 递归构建：左子树由
[1, i-1]生成，右子树由[i+1, n]生成。
完整的规范代码
class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right def generateTrees(n): """ 递归分治法生成所有可能的二叉搜索树 :param n: int, 二叉搜索树中的节点数 :return: List[TreeNode], 所有的二叉搜索树的列表 """ if n == 0: return [] def build_trees(start, end): if start > end: return [None] # 必须返回包含 None 的列表，以便在上一级递归中进行循环 all_trees = [] for i in range(start, end + 1): # 枚举可行根节点 # 获得所有可行的左子树集 left_trees = build_trees(start, i - 1) # 获得所有可行的右子树集 right_trees = build_trees(i + 1, end) # 从左子树集和右子树集中选出一棵左子树和一棵右子树，然后拼接到根节点 for l in left_trees: for r in right_trees: current_tree = TreeNode(i) current_tree.left = l current_tree.right = r all_trees.append(current_tree) return all_trees return build_trees(1, n) # 示例调用 result = generateTrees(3)
算法分析
- 时间复杂度：(O(4^n / n^1.5))，基于卡特兰数的特性。
- 空间复杂度：(O(4^n / n^1.5))，因为存储了所有可能的二叉搜索树。
方法二：动态规划
解题步骤
- 初始化：使用一个列表
dp，其中dp[i]存储所有包含i个节点的不同 BST。 - 动态规划填表：对于每个
i，通过拼接dp[j-1]（左子树）和dp[i-j]（右子树）的所有可能组合来构建。
完整的规范代码
def generateTrees(n): if n == 0: return [] dp = [[] for _ in range(n + 1)] dp[0] = [None] for i in range(1, n + 1): for j in range(1, i + 1): for left in dp[j - 1]: for right in dp[i - j]: root = TreeNode(j) root.left = left root.right = clone(right, j) # 克隆右子树并偏移节点值 dp[i].append(root) return dp[n] def clone(node, offset): if not node: return None root = TreeNode(node.val + offset) root.left = clone(node.left, offset) root.right = clone(node.right, offset) return root
算法分析
- 时间复杂度：(O(4^n / n^1.5))，这与第一种方法的时间复杂度相同，因为基本操作和卡特兰数的特性类似。
- 空间复杂度：(O(4^n / n^1.5))，存储所有可能的二叉搜索树。
方法三：记忆化递归
解题步骤
- 记忆化存储：使用字典或列表来缓存已计算的结果，避免重复计算相同的子问题。
- 递归构建：递归过程中检查是否已生成当前范围的二叉树，若已存在则直接返回。
完整的规范代码
def generateTrees(n): memo = {} def build_trees(start, end): if start > end: return [None] if (start, end) in memo: return memo[(start, end)] all_trees = [] for i in range(start, end + 1): left_trees = build_trees(start, i - 1) right_trees = build_trees(i + 1, end) for l in left_trees: for r in right_trees: root = TreeNode(i) root.left = l root.right = r all_trees.append(root) memo[(start, end)] = all_trees return all_trees return build_trees(1, n) if n else [] # 示例调用 result = generateTrees(3)
算法分析
- 时间复杂度：(O(4^n / n^1.5))，利用记忆化存储减少了重复计算。
- 空间复杂度：(O(4^n / n^1.5))，用于存储所有可能的二叉搜索树以及记忆化的开销。
方法四：动态规划优化构建方式
解题步骤
- 动态规划构建：通过一个嵌套循环逐步构建所有可能的二叉树，同时使用动态规划表来记录每个节点数对应的所有可能树。
- 利用已有树进行构建：对于每个
i，利用之前构建的树通过复制并调整指针来创建新的树。
完整的规范代码
def generateTrees(n): if n == 0: return [] dp = [[None] * (n + 1) for _ in range(n + 1)] for length in range(1, n + 1): for start in range(1, n - length + 2): end = start + length - 1 dp[start][end] = [] for root_val in range(start, end + 1): for left in dp[start][root_val - 1]: for right in dp[root_val + 1][end]: root = TreeNode(root_val) root.left = left root.right = right dp[start][end].append(root) return dp[1][n]
算法分析
- 时间复杂度：(O(4^n / n^1.5))，每个子问题都是独立计算。
- 空间复杂度：(O(4^n / n^1.5))，动态规划表存储了所有中间结果。
不同算法的优劣势对比
| 特征 | 方法一：递归分治法 | 方法二：动态规划 | 方法三：记忆化递归 | 方法四：动态规划优化构建方式 |
| 时间复杂度 | (O(4^n / n^1.5)) | (O(4^n / n^1.5)) | (O(4^n / n^1.5)) | (O(4^n / n^1.5)) |
| 空间复杂度 | (O(4^n / n^1.5)) | (O(4^n / n^1.5)) | (O(4^n / n^1.5)) | (O(4^n / n^1.5)) |
| 优势 | 直观、容易理解 | 结构清晰、易于实现 | 减少重复计算、提高效率 | 利用已构建的树，提高构建效率 |
| 劣势 | 计算重复，效率低 | 空间占用大 | 空间占用大，较复杂 | 实现复杂，需要维护大量状态 |
应用示例
这些生成二叉搜索树的方法可以应用于算法设计与数据结构教学、计算机视觉中的决策树构建、以及任何需要生成多种状态树的应用中。
欢迎关注微信公众号 数据分析螺丝钉
