LeetCode 题目 95:从递归到动态规划实现 不同的二叉搜索树 II

devtools/2024/12/22 16:12:13/

本文探讨了多种生成所有可能二叉搜索树的算法,包括递归分治法、动态规划、记忆化递归,详解每种方法的实现及优劣势。

题目描述

给定一个整数 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 的根节点。


方法一:递归分治法

解题步骤
  1. 分治策略:对于每个数 i,使其为根节点,然后递归地生成所有可能的左子树和右子树。
  2. 递归构建:左子树由 [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)),因为存储了所有可能的二叉搜索树。

方法二:动态规划

解题步骤
  1. 初始化:使用一个列表 dp,其中 dp[i] 存储所有包含 i 个节点的不同 BST。
  2. 动态规划填表:对于每个 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)),存储所有可能的二叉搜索树。

方法三:记忆化递归

解题步骤
  1. 记忆化存储:使用字典或列表来缓存已计算的结果,避免重复计算相同的子问题。
  2. 递归构建:递归过程中检查是否已生成当前范围的二叉树,若已存在则直接返回。
完整的规范代码
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)),用于存储所有可能的二叉搜索树以及记忆化的开销。

方法四:动态规划优化构建方式

解题步骤
  1. 动态规划构建:通过一个嵌套循环逐步构建所有可能的二叉树,同时使用动态规划表来记录每个节点数对应的所有可能树。
  2. 利用已有树进行构建:对于每个 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))
优势直观、容易理解结构清晰、易于实现减少重复计算、提高效率利用已构建的树,提高构建效率
劣势计算重复,效率低空间占用大空间占用大,较复杂实现复杂,需要维护大量状态

应用示例

这些生成二叉搜索树的方法可以应用于算法设计与数据结构教学、计算机视觉中的决策树构建、以及任何需要生成多种状态树的应用中。


http://www.ppmy.cn/devtools/31488.html

相关文章

特斯拉PIXCELL矩阵大灯擎耀远程控制技术照亮未来智能之光

在科技的浪潮中,特斯拉这个名字如同一道闪电,照亮了新能源汽车的天空。而在这片星空中,特斯拉PIXCELL矩阵大灯则如同一颗璀璨的星辰,以其独特的创新技术和卓越的性能,为驾驶者提供了前所未有的照明体验。矩阵大灯技术如…

Topaz Gigapixel AI for Mac:图像放大的艺术

在数字图像的世界里,Topaz Gigapixel AI for Mac如同一把魔法棒,将低分辨率的图像瞬间变为高清细腻的艺术品。这款软件采用了先进的人工智能算法,深度分析图像中的每一个细节,然后通过智能插值和重构技术,将图像放大至…

02-Shell编程-Linux用户和组

Shell脚本实现编程管理Linux用户和组脚本,编写思路如下: (1)脚本支持创建普通用户。 (2)支持创建多个用户或者列表用户添加。 (3)支持Linux系统用户删除。 (4&#xf…

从零开始搭建一个vue项目

从零开始搭建一个vue项目 一、环境准备 1.1 安装node.js 选择合适的LTS版本,然后下载安装,安装地址:https://nodejs.org/en/download 在命令行中查看已安装的node.js版本 node -v v14.14.01.2 切换为淘宝的镜像源 解决国内下载慢的问题,…

qt5-入门-2D绘图-Graphics View 架构

参考: Qt Graphics View Framework_w3cschool https://www.w3cschool.cn/learnroadqt/4mvj1j53.html C GUI Programming with Qt 4, Second Edition 本地环境: win10专业版,64位,Qt 5.12 基础知识 QPainter比较适合少量绘图的情…

服务器数据恢复—异常断电导致RAID模块故障的数据恢复案例

服务器数据恢复环境: 某品牌ProLiant DL380系列服务器,服务器中有一组由6块SAS硬盘组建的RAID5阵列,WINDOWS SERVER操作系统,作为企业内部文件服务器使用。 服务器故障: 机房供电几次意外中断,服务器出现故…

Apache SSI远程命令执行漏洞

什么是SSI Apache SSI(Server Side Include),通常称为"服务器端嵌入"或者叫"服务器端包含",是一种类似于ASP的基于服务器的网页制作技术。默认扩展名是 .stm、.shtm 和 .shtml。 从技术层面来讲,SSI是一种在静…

【漏洞复现】zookeeper AdminServer 未授权访问漏洞

0x01 产品简介 ZooKeeper 是一个集中式服务,用于维护配置信息、命名、提供分布式同步和提供组服务。ZooKeeper的AdminServer是其管理界面的一部分,通常用于监控ZooKeeper集群的状态和执行一些管理操作。AdminServer提供了Web-based的管理和监控功能&…