本文探讨了多种生成所有可能二叉搜索树的算法，包括递归分治法、动态规划、记忆化递归，详解每种方法的实现及优劣势。
题目描述
给定一个整数 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)) |
| 优势 | 直观、容易理解 | 结构清晰、易于实现 | 减少重复计算、提高效率 | 利用已构建的树，提高构建效率 |
| 劣势 | 计算重复，效率低 | 空间占用大 | 空间占用大，较复杂 | 实现复杂，需要维护大量状态 |
应用示例
这些生成二叉搜索树的方法可以应用于算法设计与数据结构教学、计算机视觉中的决策树构建、以及任何需要生成多种状态树的应用中。