LeetCode题练习与总结:不同的二叉搜索树Ⅱ--95
一、题目描述
给你一个整数 n ,请你生成并返回所有由 n 个节点组成且节点值从 1 到 n 互不相同的不同 二叉搜索树 。可以按 任意顺序 返回答案。
示例 1:

输入:n = 3 输出:[[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]
示例 2:
输入:n = 1 输出:[[1]]
提示:
1 <= n <= 8
二、解题思路
我们可以使用递归的方法来解决这个问题。递归的基本思想是,对于每个数i,作为根节点,其左子树由[1, i-1]构成,其右子树由[i+1, n]构成。对于左子树和右子树,我们又可以应用同样的方法来生成所有可能的BST。
- 递归基准情况: 如果n小于1,那么没有节点可以用来构建树,返回空列表。
- 递归分解: 对于每个数i,作为可能的根节点,递归地为左子树和右子树生成所有可能的BST。
- 合并结果: 对于每个根节点i,我们需要将所有可能的左子树和右子树进行组合,得到所有可能的BST。
三、具体代码
import java.util.List;
import java.util.ArrayList;public class Solution {public List<TreeNode> generateTrees(int n) {if (n == 0) {return new ArrayList<>();}return generateSubtrees(1, n);}private List<TreeNode> generateSubtrees(int start, int end) {List<TreeNode> subtrees = new ArrayList<>();if (start > end) {subtrees.add(null); // 添加空树作为递归基准情况return subtrees;}for (int i = start; i <= end; i++) {// 生成所有可能的左子树List<TreeNode> leftSubtrees = generateSubtrees(start, i - 1);// 生成所有可能的右子树List<TreeNode> rightSubtrees = generateSubtrees(i + 1, end);// 将左子树和右子树与根节点i组合for (TreeNode left : leftSubtrees) {for (TreeNode right : rightSubtrees) {TreeNode root = new TreeNode(i);root.left = left;root.right = right;subtrees.add(root);}}}return subtrees;}
}
四、时间复杂度和空间复杂度
1. 时间复杂度
时间复杂度的分析基于每个节点作为根节点时,生成所有可能的左子树和右子树的组合。
-
对于每个节点i作为根节点,左子树的可能数为i-1,右子树的可能数为n-i。
-
对于每个节点i,我们需要进行(i-1)*(n-i)次操作来生成所有可能的左子树和右子树的组合。
-
因为我们需要对1到n的每个数都作为根节点进行这样的操作,所以总的时间复杂度为:
这是因为对于每个节点i,我们都在进行近似n^2次操作,而这样的操作要进行n次。
因此,时间复杂度是O(n^3)。
2. 空间复杂度
空间复杂度的分析基于递归调用栈的深度以及存储所有生成的树结构的空间。
(1)递归调用栈的深度:递归调用栈的最大深度是O(n),因为每次递归都会减少一个数字直到没有数字剩余。
(2)存储所有生成的树结构的空间:
- 总共有卡特兰数C(n)个不同的二叉搜索树。
- 每个树的结构最多有O(n)个节点。
- 因此,总的空间复杂度是O(n) * C(n)。
卡特兰数C(n)的增长速度是O(4^n / n^1.5),所以总的空间复杂度是O(n) * O(4^n / n^1.5) = O(4^n / n^0.5)。
因此,该算法的时间复杂度是O(n^3),空间复杂度是O(4^n / n^0.5)。
五、总结知识点
-
递归:代码中使用了递归函数
generateSubtrees来生成所有可能的二叉搜索树。递归是一种常用的算法设计技巧,它允许函数调用自身来解决问题的一个较小部分,直到达到一个基准情况。 -
二叉搜索树(BST)的性质:二叉搜索树是一种特殊的二叉树,其中每个节点的值都大于其左子树的所有节点的值,且小于其右子树的所有节点的值。代码中利用了这个性质来生成所有可能的BST。
-
列表(List)的使用:Java中的
List接口用于存储有序的集合,代码中使用了ArrayList来实现这个接口。列表用于存储生成的子树和最终的树集合。 -
循环和条件语句:代码中使用了
for循环来遍历可能的根节点值,并使用了if语句来判断递归的基准情况。 -
树的结构:代码中定义了
TreeNode类来表示树的节点,每个节点包含一个值和指向其左右子节点的引用。 -
动态规划思想:虽然代码中没有显式地使用动态规划,但是递归方法中隐含了动态规划的思想,即通过解决子问题来构建整个问题的解决方案,并且存储这些子问题的解以避免重复计算。
-
函数定义和返回值:代码中定义了两个函数:
generateTrees是公共接口,generateSubtrees是私有辅助函数。generateSubtrees函数返回一个包含所有可能的子树的列表。 -
空树的处理:在递归的基准情况中,代码添加了一个空树(
null)到子树列表中。这表示没有更多的节点可以用来构建树,是递归终止的条件。 -
组合问题的解决:代码通过两层循环来组合左子树和右子树,这是一种常见的解决组合问题的方法。
以上就是解决这个问题的详细步骤,希望能够为各位提供启发和帮助。
相关文章:
LeetCode题练习与总结:不同的二叉搜索树Ⅱ--95
一、题目描述 给你一个整数 n ,请你生成并返回所有由 n 个节点组成且节点值从 1 到 n 互不相同的不同 二叉搜索树 。可以按 任意顺序 返回答案。 示例 1: 输入:n 3 输出:[[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,nul…...
idea SpringBoot + Gradle 环境配置到项目打包
一、前言 Gradle是一个基于Apache Ant和Apache Maven概念的项目自动化构建开源工具。它使用一种基于Groovy的特定领域语言(DSL)来声明项目设置,也增加了基于Kotlin语言的kotlin-based DSL,抛弃了基于XML的各种繁琐配置。 面向Java应用为主。当前其支持…...
深入理解tengine的sysguard模块
目录 1. 引言2. 开启sysguard模块2.1 编译2.2 配置3. 源码分析3.1 配置参数分析3.2 模块的初始化3.3 ngx_http_sysguard_handler函数3.4 各项负载指标的获取3.4.1 load系统负载的获取3.4.2 cpu使用率的获取3.4.3 内存使用情况的获取3.3.5 请求平均响应时间的获取1. 引言 Tengin…...
探索多模态LLM作为驾驶的世界模型
24年5月MIT的论文“Probing Multimodal LLMs as World Models for Driving”。 主要对多模态大语言模型(MLLM)在自动驾驶领域的应用进行了审视,并挑战/验证了一些常见的假设,重点关注它们通过图像/帧序列推理和解释在闭环控制环境…...
掌握Vim:Linux系统维护的瑞士军刀 - 常用命令深度解析
在Linux的世界里,Vim编辑器犹如一位沉默的剑客,它的命令就是那锋利的剑刃,能够在代码的海洋中劈波斩浪。对于每一位Linux系统用户来说,掌握Vim的常用命令,就如同获得了维护系统的瑞士军刀。今天,让我们一起…...
C++数组和指针应用实例 -- 实现计算器
C 的数组和C 语言一样,C完全兼容C语言的指针,但是会多出一个this指针 用C实现计算器 case1: 基本实现: #include <iostream>using namespace std;int add(int a,int b) {return ab; }int minu(int a,int b) {return a-b; }int mul(int a,int b) …...
【多电压流程 Multivoltage Flow】- 5.特定工具使用建议(6.Formality)
使用Formality进行形式验证 Formality支持具有低功耗特性的功能等效性检查,如时钟门控、多阈值电压(multiple-Vt)、多电压供电、电源门控以及动态电压和频率缩放。Formality能够识别低功耗单元,例如隔离单元、电平转换器、始终开启单元、保持寄存器和电源门。 Formality支持…...
力扣 72. 编辑距离 python AC
动态规划 class Solution:def minDistance(self, word1, word2):size1 len(word1)size2 len(word2)dp [[0] * (size2 1) for _ in range(size1 1)]for i in range(1, size1 1):dp[i][0] dp[i - 1][0] 1for i in range(1, size2 1):dp[0][i] dp[0][i - 1] 1for i in…...
vue 发布项目
You are not allowed to force push code to a protected branch on this project. 分支做了保护,git中设置允许强制推送...
springBoot实现发送邮箱验证码 redis缓存源码
要在Spring Boot中实现发送邮箱验证码并使用Redis进行缓存,你需要遵循几个步骤。以下是一个简化的示例,展示了如何整合这些功能: 添加依赖 首先,确保你的pom.xml(Maven)或build.gradle(Gradle…...
QT--4
QT 使用定时器完成闹钟 #include "widget.h" #include "ui_widget.h"void Widget::timestart() {timer.start(1000); }void Widget::timeend() {timer.stop(); }Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(t…...
感染了后缀为.360勒索病毒如何应对?数据能够恢复吗?
导言: 在数字化时代的浪潮中,网络安全问题如同暗流涌动,威胁着每一个互联网用户的安宁。而近年来,一种名为.360勒索病毒的新型网络威胁逐渐浮出水面,以其独特的加密方式和狡猾的传播策略,给全球网络安全带…...
JavaSE多态
多态:一个对象在不同条件下表示的不同形态就叫多态。在程序中,多态是父类引用指定子类对象就叫多态。 多态是面向对象程序设计中的第三个特征 // 多态 class Father {String name;public void desc() {System.out.println("----------");Sys…...
M 有效算法
M 有效算法 本题考验二分知识,思路是二分k的取值,就按第一组样例来说当我们k取值为1的时候我们遍历数组想让|8-x|<k1的话x的取值范围是7-9,想让|3-x|<k2的话x的取值范围是1-5,两者x的区间不重合,说明肯定没有x能…...
知识付费系统制作,托管机构如何提高体验课转化率?要注意什么?
现在托管机构非常流行,一所学校周边就会出现好几家托管机构,所以竞争非常激烈。很多托管机构为了扩大生源,会选择体验课来让学生体验,至于如何提高体验课转化率,就看机构的本事了。 1、市场调研:摸清当前我…...
【iOS逆向与安全】网上gw如何自动登录与签到SM2,SM3,SM4算法加解密
1.下载 app 2.frida 调试 3.抓包查看接口 4.分析加密数据 5.易语言编写代码 1 .开始下载 下载好发现有越狱检测,检测点为: -[AppDelegate isJailBreak]; 于是编写插件xm代码 : %hook AppDelegate- (void)isJailBreak{NSLog("AppDelegate is…...
《CKA/CKAD应试指南/从docker到kubernetes 完全攻略》学习笔记 第14章 包管理helm v3
前言 考试大纲: 了解helm是如何工作的,从而实现快速部署应用 本章要点: 考点1:添加helm源 考点2:使用helm 部署应用 前面在使用wordpress + mysql 部署博客应用的时候,需要做许多工作,需要每个pod创建pv和pvc,然后分别创建每个应用pod及svc,整个过程非常麻烦. 如果搭建博客的…...
蓝桥杯备战.19有奖问答dfs
P9230 [蓝桥杯 2023 省 A] 填空问题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) #include<bits/stdc.h> using namespace std; #define endl \n //#define int long long const int N 2e510; int a[N],w[N]; int ans 0; void dfs(int score,int cnt) {if(cnt>3…...
【JS红宝书学习笔记】第1、2章 初识JS
第1章 什么是JavaScript JavaScript 是一门用来与网页交互的脚本语言,包含以下三个组成部分。 ECMAScript:由 ECMA-262 定义并提供核心功能。文档对象模型(DOM):提供与网页内容交互的方法和接口。浏览器对象模型&…...
学习java
在实验室看见这本书,无聊看了下,写出了第一个java代码 成功下载了eclipse并且汉化。 写了自己的第一个java程序: package ttttt;public class ttttt {public static void main(String[] args) {System.out.println("hello world")…...
电脑插入多块移动硬盘后经常出现卡顿和蓝屏
当电脑在插入多块移动硬盘后频繁出现卡顿和蓝屏问题时,可能涉及硬件资源冲突、驱动兼容性、供电不足或系统设置等多方面原因。以下是逐步排查和解决方案: 1. 检查电源供电问题 问题原因:多块移动硬盘同时运行可能导致USB接口供电不足&#x…...
屋顶变身“发电站” ,中天合创屋面分布式光伏发电项目顺利并网!
5月28日,中天合创屋面分布式光伏发电项目顺利并网发电,该项目位于内蒙古自治区鄂尔多斯市乌审旗,项目利用中天合创聚乙烯、聚丙烯仓库屋面作为场地建设光伏电站,总装机容量为9.96MWp。 项目投运后,每年可节约标煤3670…...
成都鼎讯硬核科技!雷达目标与干扰模拟器,以卓越性能制胜电磁频谱战
在现代战争中,电磁频谱已成为继陆、海、空、天之后的 “第五维战场”,雷达作为电磁频谱领域的关键装备,其干扰与抗干扰能力的较量,直接影响着战争的胜负走向。由成都鼎讯科技匠心打造的雷达目标与干扰模拟器,凭借数字射…...
Android Bitmap治理全解析:从加载优化到泄漏防控的全生命周期管理
引言 Bitmap(位图)是Android应用内存占用的“头号杀手”。一张1080P(1920x1080)的图片以ARGB_8888格式加载时,内存占用高达8MB(192010804字节)。据统计,超过60%的应用OOM崩溃与Bitm…...
MySQL用户和授权
开放MySQL白名单 可以通过iptables-save命令确认对应客户端ip是否可以访问MySQL服务: test: # iptables-save | grep 3306 -A mp_srv_whitelist -s 172.16.14.102/32 -p tcp -m tcp --dport 3306 -j ACCEPT -A mp_srv_whitelist -s 172.16.4.16/32 -p tcp -m tcp -…...
Python Ovito统计金刚石结构数量
大家好,我是小马老师。 本文介绍python ovito方法统计金刚石结构的方法。 Ovito Identify diamond structure命令可以识别和统计金刚石结构,但是无法直接输出结构的变化情况。 本文使用python调用ovito包的方法,可以持续统计各步的金刚石结构,具体代码如下: from ovito…...
uniapp手机号一键登录保姆级教程(包含前端和后端)
目录 前置条件创建uniapp项目并关联uniClound云空间开启一键登录模块并开通一键登录服务编写云函数并上传部署获取手机号流程(第一种) 前端直接调用云函数获取手机号(第三种)后台调用云函数获取手机号 错误码常见问题 前置条件 手机安装有sim卡手机开启…...
Monorepo架构: Nx Cloud 扩展能力与缓存加速
借助 Nx Cloud 实现项目协同与加速构建 1 ) 缓存工作原理分析 在了解了本地缓存和远程缓存之后,我们来探究缓存是如何工作的。以计算文件的哈希串为例,若后续运行任务时文件哈希串未变,系统会直接使用对应的输出和制品文件。 2 …...
Element-Plus:popconfirm与tooltip一起使用不生效?
你们好,我是金金金。 场景 我正在使用Element-plus组件库当中的el-popconfirm和el-tooltip,产品要求是两个需要结合一起使用,也就是鼠标悬浮上去有提示文字,并且点击之后需要出现气泡确认框 代码 <el-popconfirm title"是…...
Git 命令全流程总结
以下是从初始化到版本控制、查看记录、撤回操作的 Git 命令全流程总结,按操作场景分类整理: 一、初始化与基础操作 操作命令初始化仓库git init添加所有文件到暂存区git add .提交到本地仓库git commit -m "提交描述"首次提交需配置身份git c…...
