本文探讨了多种生成所有可能二叉搜索树的算法,包括递归分治法、动态规划、记忆化递归,详解每种方法的实现及优劣势。
题目描述
给定一个整数 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]
生成。
完整的规范代码
python">class TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightdef 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 = lcurrent_tree.right = rall_trees.append(current_tree)return all_treesreturn 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]
(右子树)的所有可能组合来构建。
完整的规范代码
python">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 = leftroot.right = clone(right, j) # 克隆右子树并偏移节点值dp[i].append(root)return dp[n]def clone(node, offset):if not node:return Noneroot = 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)),存储所有可能的二叉搜索树。
方法三:记忆化递归
解题步骤
- 记忆化存储:使用字典或列表来缓存已计算的结果,避免重复计算相同的子问题。
- 递归构建:递归过程中检查是否已生成当前范围的二叉树,若已存在则直接返回。
完整的规范代码
python">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 = lroot.right = rall_trees.append(root)memo[(start, end)] = all_treesreturn all_treesreturn build_trees(1, n) if n else []# 示例调用
result = generateTrees(3)
算法分析
- 时间复杂度:(O(4^n / n^1.5)),利用记忆化存储减少了重复计算。
- 空间复杂度:(O(4^n / n^1.5)),用于存储所有可能的二叉搜索树以及记忆化的开销。
方法四:动态规划优化构建方式
解题步骤
- 动态规划构建:通过一个嵌套循环逐步构建所有可能的二叉树,同时使用动态规划表来记录每个节点数对应的所有可能树。
- 利用已有树进行构建:对于每个
i
,利用之前构建的树通过复制并调整指针来创建新的树。
完整的规范代码
python">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 - 1dp[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 = leftroot.right = rightdp[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)) |
优势 | 直观、容易理解 | 结构清晰、易于实现 | 减少重复计算、提高效率 | 利用已构建的树,提高构建效率 |
劣势 | 计算重复,效率低 | 空间占用大 | 空间占用大,较复杂 | 实现复杂,需要维护大量状态 |
应用示例
这些生成二叉搜索树的方法可以应用于算法设计与数据结构教学、计算机视觉中的决策树构建、以及任何需要生成多种状态树的应用中。