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")…...
SkyWalking 10.2.0 SWCK 配置过程
SkyWalking 10.2.0 & SWCK 配置过程 skywalking oap-server & ui 使用Docker安装在K8S集群以外,K8S集群中的微服务使用initContainer按命名空间将skywalking-java-agent注入到业务容器中。 SWCK有整套的解决方案,全安装在K8S群集中。 具体可参…...
Qt Widget类解析与代码注释
#include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this); }Widget::~Widget() {delete ui; }//解释这串代码,写上注释 当然可以!这段代码是 Qt …...
【解密LSTM、GRU如何解决传统RNN梯度消失问题】
解密LSTM与GRU:如何让RNN变得更聪明? 在深度学习的世界里,循环神经网络(RNN)以其卓越的序列数据处理能力广泛应用于自然语言处理、时间序列预测等领域。然而,传统RNN存在的一个严重问题——梯度消失&#…...
linux 错误码总结
1,错误码的概念与作用 在Linux系统中,错误码是系统调用或库函数在执行失败时返回的特定数值,用于指示具体的错误类型。这些错误码通过全局变量errno来存储和传递,errno由操作系统维护,保存最近一次发生的错误信息。值得注意的是,errno的值在每次系统调用或函数调用失败时…...
【论文笔记】若干矿井粉尘检测算法概述
总的来说,传统机器学习、传统机器学习与深度学习的结合、LSTM等算法所需要的数据集来源于矿井传感器测量的粉尘浓度,通过建立回归模型来预测未来矿井的粉尘浓度。传统机器学习算法性能易受数据中极端值的影响。YOLO等计算机视觉算法所需要的数据集来源于…...
AI编程--插件对比分析:CodeRider、GitHub Copilot及其他
AI编程插件对比分析:CodeRider、GitHub Copilot及其他 随着人工智能技术的快速发展,AI编程插件已成为提升开发者生产力的重要工具。CodeRider和GitHub Copilot作为市场上的领先者,分别以其独特的特性和生态系统吸引了大量开发者。本文将从功…...
图表类系列各种样式PPT模版分享
图标图表系列PPT模版,柱状图PPT模版,线状图PPT模版,折线图PPT模版,饼状图PPT模版,雷达图PPT模版,树状图PPT模版 图表类系列各种样式PPT模版分享:图表系列PPT模板https://pan.quark.cn/s/20d40aa…...
python执行测试用例,allure报乱码且未成功生成报告
allure执行测试用例时显示乱码:‘allure’ �����ڲ����ⲿ���Ҳ���ǿ�&am…...
GO协程(Goroutine)问题总结
在使用Go语言来编写代码时,遇到的一些问题总结一下 [参考文档]:https://www.topgoer.com/%E5%B9%B6%E5%8F%91%E7%BC%96%E7%A8%8B/goroutine.html 1. main()函数默认的Goroutine 场景再现: 今天在看到这个教程的时候,在自己的电…...
uniapp 小程序 学习(一)
利用Hbuilder 创建项目 运行到内置浏览器看效果 下载微信小程序 安装到Hbuilder 下载地址 :开发者工具默认安装 设置服务端口号 在Hbuilder中设置微信小程序 配置 找到运行设置,将微信开发者工具放入到Hbuilder中, 打开后出现 如下 bug 解…...
