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