当前位置: 首页 > news >正文

day22 ● 235. 二叉搜索树的最近公共祖先 ● 701.二叉搜索树中的插入操作 ● 450.删除二叉搜索树中的节点

问题:

● 235. 二叉搜索树的最近公共祖先
● 701.二叉搜索树中的插入操作
● 450.删除二叉搜索树中的节点

首先,二叉搜索树是一种常见的数据结构,它具有以下特点:

  1. 每个节点最多有两个子节点,分别为左子节点和右子节点;
  2. 左子节点的值小于父节点的值,右子节点的值大于父节点的值;
  3. 没有重复的节点值。

在刷题过程中,我遇到了以下三道题目:

    1. 二叉搜索树的最近公共祖先:该题目要求在一个二叉搜索树中,找到两个节点的最近公共祖先。我的解题思路是,从根节点开始遍历二叉搜索树,如果两个节点的值都小于当前节点的值,说明它们都在当前节点的左子树中;如果两个节点的值都大于当前节点的值,说明它们都在当前节点的右子树中;如果一个节点的值小于当前节点的值,另一个节点的值大于当前节点的值,说明它们的最近公共祖先就是当前节点。具体实现可以使用递归或者迭代方式,时间复杂度为O(logn)。
    1. 二叉搜索树中的插入操作:该题目要求在一个二叉搜索树中插入一个节点。我的解题思路是,从根节点开始遍历二叉搜索树,如果插入节点的值小于当前节点的值,就去遍历左子树;如果插入节点的值大于当前节点的值,就去遍历右子树。一直遍历到某个节点的左子节点或右子节点为空时,就把插入节点作为该节点的左子节点或右子节点。具体实现可以使用递归或者迭代方式,时间复杂度为O(logn)。
    1. 删除二叉搜索树中的节点:该题目要求在一个二叉搜索树中删除一个节点。我的解题思路是,首先找到要删除的节点,如果该节点有两个子节点,就找到它的后继节点(即右子树中最小的节点),把后继节点的值复制到要删除的节点中,然后把要删除的节点变成后继节点;如果该节点只有一个子节点或没有子节点,就直接把该节点删除,并把它的子节点接到它的父节点上。具体实现可以使用递归或者迭代方式,时间复杂度为O(logn)。

总结一下,二叉搜索树是一种非常重要的数据结构,在刷题过程中,我对它的特点和操作有了更深入的理解。对于二叉搜索树的操作,递归和迭代实现都可以,具体选择哪种方式要根据具体情况而定。在Java中,可以使用TreeNode类来表示二叉树节点,具体实现可以参考以下代码:

class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) { val = x; }
}class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if (root == null || root == p || root == q) {return root;}if (root.val > p.val && root.val > q.val) {return lowestCommonAncestor(root.left, p, q);} else if (root.val < p.val && root.val < q.val) {return lowestCommonAncestor(root.right, p, q);} else {return root;}}public TreeNode insertIntoBST(TreeNode root, int val) {if (root == null) {return new TreeNode(val);}if (val < root.val) {root.left = insertIntoBST(root.left, val);} else {root.right = insertIntoBST(root.right, val);}return root;}public TreeNode deleteNode(TreeNode root, int key) {if (root == null) {return null;}if (key < root.val) {root.left = deleteNode(root.left, key);} else if (key > root.val) {root.right = deleteNode(root.right, key);} else {if (root.left == null) {return root.right;} else if (root.right == null) {return root.left;} else {TreeNode minNode = getMin(root.right);root.val = minNode.val;root.right = deleteNode(root.right, minNode.val);}}return root;}public TreeNode getMin(TreeNode node) {while (node.left != null) {node = node.left;}return node;}
}

相关文章:

day22 ● 235. 二叉搜索树的最近公共祖先 ● 701.二叉搜索树中的插入操作 ● 450.删除二叉搜索树中的节点

问题&#xff1a; ● 235. 二叉搜索树的最近公共祖先 ● 701.二叉搜索树中的插入操作 ● 450.删除二叉搜索树中的节点 首先&#xff0c;二叉搜索树是一种常见的数据结构&#xff0c;它具有以下特点&#xff1a; 每个节点最多有两个子节点&#xff0c;分别为左子节点和右子节…...

ChatGPT 这个风口,普通人怎么抓住?

最近在测试ChatGPT不同领域的变现玩法&#xff0c;有一些已经初见成效&#xff0c;接下来会慢慢分享出来。 今天先给大家分享一个&#xff0c;看完就能直接上手的暴力引流玩法。 所需工具&#xff1a; 1&#xff09;ChatGPT&#xff08;最好是plus版&#xff0c;需要保证快速…...

Python代码规范:企业级代码静态扫描-代码规范、逻辑、语法、安全检查,以及代码规范自动编排(2)

本篇将总结实际项目开发中Python代码规范检查、自动编排的一些工具&#xff0c;特点&#xff0c;使用方法&#xff0c;以及如何在Pycharm中集成这些工具&#xff0c;如autoflake、yapf、black、isort、autopep8代码规范和自动编排工具。上一篇总结的pylint、pyproject-flake8、…...

acme.sh从 letsencrypt 生成SSL免费证书并自动更新证书

acme.sh 实现了 acme 协议, 可以从 letsencrypt 生成免费的证书 ACME 协议: Automatic Certificate Management Environment 自动化证书管理环境 文档: github: https://github.com/acmesh-official/acme.shgitee: https://gitee.com/neilpang/acme.sh中文文档: https://git…...

基于html+css的evenly布局

准备项目 项目开发工具 Visual Studio Code 1.44.2 版本: 1.44.2 提交: ff915844119ce9485abfe8aa9076ec76b5300ddd 日期: 2020-04-16T16:36:23.138Z Electron: 7.1.11 Chrome: 78.0.3904.130 Node.js: 12.8.1 V8: 7.8.279.23-electron.0 OS: Windows_NT x64 10.0.19044 项目…...

【从零开始学习 UVM】10.5、UVM TLM —— UVM TLM Blocking Get Port

文章目录 UVM TLM Get Port Example1. 创建一个发送方类,其端口类型为 uvm_blocking_get_imp3. 创建接收器类,等待 get 方法。4. 在更高层次上连接端口及其实现Get端口阻塞行为任何组件都可以通过 TLM get 端口请求从另一个组件接收事务。发送组件应定义获取端口的实现。该实…...

English Learning - L2 第 10 次小组纠音 辅音 [m] [n] [ŋ] 半元音 [w] [j] 2023.3.29 周三

English Learning - L2 第 10 次小组纠音 辅音 [m] [n] [ŋ] [w] [j] 2023.3.29 周三共性问题more Autumn [ɔː] 舌位偏前gone evening 前后鼻音不分Hes proud of this name 双元音缺乏滑动感bank thing 中的后鼻音发成前鼻音week what yolk 元音 [iː] [ɒ] 舌位偏前 [əʊ] …...

从零开始实现一个C++高性能服务器框架----环境变量模块

此项目是根据sylar框架实现&#xff0c;是从零开始重写sylar&#xff0c;也是对sylar丰富与完善 项目地址&#xff1a;https://gitee.com/lzhiqiang1999/server-framework 简介 项目介绍&#xff1a;实现了一个基于协程的服务器框架&#xff0c;支持多线程、多协程协同调度&am…...

git常用命令的解释

解释git add . git add . 命令用于将当前目录下的所有文件添加到 Git 仓库的暂存区中。这个命令通常用于刚刚打开一个 Git 仓库时&#xff0c;或者用于将本地文件更新到远程仓库时。 具体来说&#xff0c;git add . 命令会将当前目录下的所有文件添加到 Git 仓库的暂存区中&am…...

DNS和CDN的区别与联系

现在互联网用户很多不能理解CDN和DNS之间的关系&#xff0c;他们之间到底有什么区别。对于这两者永远处于模糊的概念。其实二者是相辅相成的&#xff0c;二者搭配起来能使网站更加安全&#xff0c;快速。 用户访问未使用CDN缓存网站的过程为: 1、用户向浏览器提供要访问的域名…...

Java基础知识 | 常见面试题(中):面向对象基础

撰写成一问一答的形式&#xff0c;每次回答都默写&#xff0c;对比参考答案后&#xff0c;再默写出更恰当的答案。 相关内容 Java基础知识 | 常见面试题&#xff08;上&#xff09;&#xff1a;基础概念和常识 Java基础知识 | 常见面试题&#xff08;上&#xff09;&#xff1a…...

勒索软件正在从 Windows 转向 Linux

听说勒索软件正在从 Windows 转向 Linux了勒索软件正在从 Windows 转向 Linux 最近几周&#xff0c;黑客们一直在对 Linux 企业网络部署 IceFire 勒索软件&#xff0c;这是一个值得注意的转变&#xff0c;因为它曾经是一个只针对 Windows 的恶意软件。与 Windows 相比&#xf…...

信息系统项目管理师 第11章 项目成本管理

1.管理基础 1.重要性和意义 项目管理主要受范围、时间、成本、质量的约束,项目成本管理就是要确保在批准的预算内完成项目。 如果项目建设的实际成本远远超出批准的投资预算,就很容易造成成本失控。 1.对工程项目认识不足。 2.组织制度不健全。 3.方法问题 4.技术的制约 5.需…...

XML 简介

文章目录一、XML 简介二、XML 用途总结一、XML 简介 XML 被设计用来传输和存储数据。 HTML 被设计用来显示数据。 XML 指可扩展标记语言&#xff08;eXtensible Markup Language&#xff09;。 可扩展标记语言&#xff08;英语&#xff1a;Extensible Markup Language&#xf…...

ERP:华为杀入,金蝶们打颤?

配图来自Canva可画 近期&#xff0c;华为官方透露将在4月份推出自研MetaERP管理系统&#xff0c;引来不少媒体和业内人士的围观&#xff0c;紧接着关于华为“进军ERP市场”的解读更是不胫而走&#xff0c;所谓一石激起千层浪&#xff0c;此说法一出&#xff0c;直接导致了金蝶…...

Linux——总复习1

1.要注意自己处于当前那个目录位置。 2.将file1的前五行/后三行重定向、附加到file2【输出重定向】 head -5 file1 > file2 tail -3 file1 >> file2 3.ls与cat区别 ls:列出目录的目录内容&#xff0c;未指定目录&#xff0c;则列出当前工作目录的内容 -l:查…...

控制SQL*PLUS的环境和数据字典简介

可以通过使用SET命令来设置SQL*PLUS的环境变量&#xff0c;从而达到控制SQL*PLUS 环境的目的。 SET命令的格式如下&#xff1a; SET 环境变量 变量的值 可以通过使用SHOW命令来显示SQL*PLUS环境变量的配置。SHOW 命令的格式如下&#xff1a; SHOW 环境变量|ALL 下面用一个…...

Chapter11.3:MATLAB_SIMULINK在离散系统中的应用

该系列博客主要讲述Matlab软件在自动控制方面的应用&#xff0c;如无自动控制理论基础&#xff0c;请先学习自动控制系列博文&#xff0c;该系列博客不再详细讲解自动控制理论知识。 自动控制理论基础相关链接&#xff1a;https://blog.csdn.net/qq_39032096/category_10287468…...

过滤器Filter

什么是Filter&#xff1f; Filter表示过滤器&#xff0c;是JavaWeb三大组件&#xff08;Servlet、FIlter、Listener&#xff09;之一。过滤器可以把对资源的请求拦截下来&#xff0c;总而实现一些特殊的功能 使用过滤器后&#xff0c;要想访问web服务器上的资源&#xff0c;必须…...

MySQL数据同步ES的常用思路和方法

文章目录 1.同步双写2.异步双写3.定时任务4.数据订阅大家应该都在各种电商网站检索过商品,检索商品一般都是通过什么实现呢?搜索引擎Elasticsearch。 那么问题来了,商品上架,数据一般写入到MySQL的数据库中,那么用于检索的数据又是怎么同步到Elasticsearch的呢? 1.同步双…...

【杂谈】-递归进化:人工智能的自我改进与监管挑战

递归进化&#xff1a;人工智能的自我改进与监管挑战 文章目录 递归进化&#xff1a;人工智能的自我改进与监管挑战1、自我改进型人工智能的崛起2、人工智能如何挑战人类监管&#xff1f;3、确保人工智能受控的策略4、人类在人工智能发展中的角色5、平衡自主性与控制力6、总结与…...

rknn优化教程(二)

文章目录 1. 前述2. 三方库的封装2.1 xrepo中的库2.2 xrepo之外的库2.2.1 opencv2.2.2 rknnrt2.2.3 spdlog 3. rknn_engine库 1. 前述 OK&#xff0c;开始写第二篇的内容了。这篇博客主要能写一下&#xff1a; 如何给一些三方库按照xmake方式进行封装&#xff0c;供调用如何按…...

React hook之useRef

React useRef 详解 useRef 是 React 提供的一个 Hook&#xff0c;用于在函数组件中创建可变的引用对象。它在 React 开发中有多种重要用途&#xff0c;下面我将全面详细地介绍它的特性和用法。 基本概念 1. 创建 ref const refContainer useRef(initialValue);initialValu…...

Spring Boot 实现流式响应(兼容 2.7.x)

在实际开发中&#xff0c;我们可能会遇到一些流式数据处理的场景&#xff0c;比如接收来自上游接口的 Server-Sent Events&#xff08;SSE&#xff09; 或 流式 JSON 内容&#xff0c;并将其原样中转给前端页面或客户端。这种情况下&#xff0c;传统的 RestTemplate 缓存机制会…...

汽车生产虚拟实训中的技能提升与生产优化​

在制造业蓬勃发展的大背景下&#xff0c;虚拟教学实训宛如一颗璀璨的新星&#xff0c;正发挥着不可或缺且日益凸显的关键作用&#xff0c;源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例&#xff0c;汽车生产线上各类…...

微信小程序 - 手机震动

一、界面 <button type"primary" bindtap"shortVibrate">短震动</button> <button type"primary" bindtap"longVibrate">长震动</button> 二、js逻辑代码 注&#xff1a;文档 https://developers.weixin.qq…...

Python如何给视频添加音频和字幕

在Python中&#xff0c;给视频添加音频和字幕可以使用电影文件处理库MoviePy和字幕处理库Subtitles。下面将详细介绍如何使用这些库来实现视频的音频和字幕添加&#xff0c;包括必要的代码示例和详细解释。 环境准备 在开始之前&#xff0c;需要安装以下Python库&#xff1a;…...

【OSG学习笔记】Day 16: 骨骼动画与蒙皮(osgAnimation)

骨骼动画基础 骨骼动画是 3D 计算机图形中常用的技术&#xff0c;它通过以下两个主要组件实现角色动画。 骨骼系统 (Skeleton)&#xff1a;由层级结构的骨头组成&#xff0c;类似于人体骨骼蒙皮 (Mesh Skinning)&#xff1a;将模型网格顶点绑定到骨骼上&#xff0c;使骨骼移动…...

全志A40i android7.1 调试信息打印串口由uart0改为uart3

一&#xff0c;概述 1. 目的 将调试信息打印串口由uart0改为uart3。 2. 版本信息 Uboot版本&#xff1a;2014.07&#xff1b; Kernel版本&#xff1a;Linux-3.10&#xff1b; 二&#xff0c;Uboot 1. sys_config.fex改动 使能uart3(TX:PH00 RX:PH01)&#xff0c;并让boo…...

如何在最短时间内提升打ctf(web)的水平?

刚刚刷完2遍 bugku 的 web 题&#xff0c;前来答题。 每个人对刷题理解是不同&#xff0c;有的人是看了writeup就等于刷了&#xff0c;有的人是收藏了writeup就等于刷了&#xff0c;有的人是跟着writeup做了一遍就等于刷了&#xff0c;还有的人是独立思考做了一遍就等于刷了。…...