删除二叉搜索树中的节点

题目链接

删除二叉搜索树中的节点

题目描述



注意点

  • 节点值唯一
  • root 是合法的二叉搜索树
  • 节点数的范围 [0, 10000]

解答思路

  • 可以根据二叉搜索树的性质找到要删除的节点,关键是删除节点后怎么重新构建成一棵新的二叉搜索树
  • 首先要找到的是删除节点node的父节点node.parent,在删除node后,该节点树构建成一棵新的二叉搜索树,node.parent应该指向新的二叉搜索树的根节点
  • 其次删除节点对应的节点树node怎么构成一棵新的二叉搜索树,应该将node.right作为新的二叉搜索树的根节点newRoot,newRoot的右子树就是原来的右子树不变;newRoot的左子树也是原来的左子树,在此基础上,newRoot的左子树左下角的节点(newRoot此时的最小值)的左子树还要连接上node.left,不然node的左子树就会丢失
  • 需要注意的是,如果node的右子树为空,则直接将node的左子树作为新的二叉搜索树即可

代码

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public TreeNode deleteNode(TreeNode root, int key) {// 方便分析删除根节点的情况TreeNode preRoot = new TreeNode(Integer.MAX_VALUE, root, null);// key的根节点TreeNode targetRoot = preRoot;// 找到key对应节点的根节点while (targetRoot != null) {// key大于当前节点,则key肯定在targetRoot右子树中if (targetRoot.val < key) {if (targetRoot.right == null) {break;}// 找到了要删除的节点->targetRoot.rightif (targetRoot.right.val == key) {targetRoot.right = reBuildTree(targetRoot.right);break;}targetRoot = targetRoot.right;}// key小于当前节点,则key肯定在targetRoot左子树中if (targetRoot.val > key) {if (targetRoot.left == null) {break;}// 找到了要删除的节点->targetRoot.leftif (targetRoot.left.val == key) {targetRoot.left = reBuildTree(targetRoot.left);break;}targetRoot = targetRoot.left;}}return preRoot.left;}/*** 重建树,删除root,root右子树根节点作为newRoot,newRoot右子树无变化,左子树左下角节点(最小值)连接root左子树根节点*/public TreeNode reBuildTree(TreeNode root) {// 无右子树,直接将左子树作为新的树if (root.right == null) {return root.left;}TreeNode newRoot = root.right;// 右子树左下角的节点连接左子树TreeNode rightMinNode = newRoot;while (rightMinNode.left != null) {rightMinNode = rightMinNode.left;}rightMinNode.left = root.left;return newRoot;}
}

关键点

  • 删除某个节点怎么构建成新的二叉搜索树
  • 注意边界问题(节点、子树为空的情况)

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/314435.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

数智时代的AI人才粮仓模型解读白皮书(2024版)

来源&#xff1a;极客邦科技 自 2023 年上半年起&#xff0c;ChatGPT 等大模型技术蓬勃发展&#xff0c;AI 技术不断突破边界&#xff0c;展现 出惊人的潜力和发展速度。从早期的逻辑推理、专家系统&#xff0c;到如今的深度学习、神经网络&#xff0c; AI 技术显著缩小了科学…

【webrtc】Chrome和Firefox在SDP协商过程中,针对localhost的不同处理

内网下chrome端webrtc协商失败 现象 我有一个webrtc服务器在局域网内&#xff0c;使用chrome浏览器访问时&#xff0c;发现webrtc在做媒体协商时失败。 具体表现是&#xff0c;在交换sdp后&#xff0c;ice的状态是oniceconnectionstatechange: failed 但是换成Firefox浏览器…

编写Spark独立应用程序

执行本文之前&#xff0c;先搭建好spark的开发环境&#xff0c;我目前只搭建了standalone模式&#xff0c;参考链接 &#xff1a; Spark Standalone模式部署-CSDN博客 1. 安装sbt 1&#xff09;下载sbt 网址&#xff1a;https://www.scala-sbt.org/download.html &#xff0c…

设计模式——终止模式之两阶段终止模式

文章目录 1. 错误思路2. 两阶段终止模式2.1 利用 isInterrupted2.2 利用停止标记interrupt-打断park Two Phase Termination 在一个线程 T1 中如何“优雅”终止线程 T2&#xff1f;这里的【优雅】指的是给 T2 一个料理后事的机会。 1. 错误思路 使用线程对象的 stop() 方法停…

论文解读-面向高效生成大语言模型服务:从算法到系统综述

一、简要介绍 在快速发展的人工智能&#xff08;AI&#xff09;领域中&#xff0c;生成式大型语言模型&#xff08;llm&#xff09;站在了最前沿&#xff0c;彻底改变了论文与数据交互的方式。然而&#xff0c;部署这些模型的计算强度和内存消耗在服务效率方面带来了重大挑战&a…

Xinlinx FPGA内的存储器BRAM全解

目录 一、总体概述1.7系列FPGA的BRAM特点2.资源情况 二、BRAM分类1.单端口RAM2.简单双端口RAM3.真双端口RAM 三、BRAM的读写1、Primitives Output Registers读操作注意事项2.三种写数据模式&#xff08;1&#xff09;Write_First&#xff08;2&#xff09;Read_First&#xff0…

【iconv】Linux c++ 中文字符串转十六进制 GBK 编码/内码

文章目录 问题描述c 代码CMakeLists.txt参考链接 问题描述 Linux 系统默认使用的是 UTF-8 编码&#xff0c;并且 c 中没有标准库可以直接将中文字符转为 GBK 编码/内码。因此需要借助 iconv 库来实现。 在实现代码之前&#xff0c;可以在一下在线工具网站进行中文字符到各个编…

mac上安装Tomcat

1. 简介 Tomcat 是一个开源的 Java 服务器&#xff0c;它实现了 Java Servlet、JavaServer Pages&#xff08;JSP&#xff09;和Java WebSocket 技术。Tomcat 是 Apache 软件基金会的一个项目&#xff0c;是一个轻量级、高性能的 Web 容器。作为一个 Web 服务器&#xff0c;To…

前端工程化Vue使用Node.js设置国内高速npm镜像源(踩坑记录版)

前端工程化Vue使用Node.js设置国内高速npm镜像源&#xff08;踩坑记录版&#xff09; 此篇仅为踩坑记录&#xff0c;并未成功更换高速镜像源&#xff0c;实际解决方法见文末跳转链接。 1.自身源镜像 自身镜像源创建Vue项目下载速度感人 2.更改镜像源 2.1 通过命令行配置 前提…

常见的排序算法

前言 算法对于我们普通的工程师来说可算得上陌生又熟悉&#xff0c;因为在平时的业务代码中可能见到他的身影比较少&#xff0c;但在底层的代码中我们可能会经常发现排序算法的影子&#xff0c;如数据库索引&#xff0c;操作系统的进程调度。因此&#xff0c;掌握这种算法中的…

打造智能语音机器人-用语音控制机器人

人工智能现已成为国家发展重大战略&#xff0c;智能语音技术作为人工智能产业链上的关键一环&#xff0c;AI应用成熟的技术之一&#xff0c;人工智能的发展也进入了一个崭新的阶段。那么打造智能语音机器人怎样实现用语音控制机器人呢&#xff1f;和小编一起来看看。 选择合适的…

Xcode for Mac:强大易用的集成开发环境

Xcode for Mac是一款专为苹果开发者打造的集成开发环境&#xff08;IDE&#xff09;&#xff0c;它集成了代码编辑器、编译器、调试器等一系列开发工具&#xff0c;让开发者能够在同一界面内完成应用的开发、测试和调试工作。 Xcode for Mac v15.2正式版下载 Xcode支持多种编程…

如何将web content项目导入idea并部署到tomcat

将Web Content项目导入IntelliJ IDEA并部署到Tomcat主要涉及以下几个步骤&#xff1a; 1. 导入Web Content项目 打开IntelliJ IDEA。选择“File” -> “New” -> “Project from Existing Sources…”。浏览到你的Web Content项目的文件夹&#xff0c;并选择它。Intell…

1.C++入门(上)

目录 1.C关键字 2.命名空间 作用域方面的优化 a.命名空间定义 b.命名空间使用 3.C 输入&输出 1.C关键字 C有63个关键字&#xff0c;C语言有32个关键字&#xff0c;存在重叠如荧光笔标出 2.命名空间 作用域方面的优化 如果变量&#xff0c;函数和类的名称都存在于全…

Hive服务详解

Hive服务 HiveServer2、Hive Metastore 服务服务共同构成了 Hive 生态系统中的核心功能&#xff0c;分别负责管理元数据和提供数据查询服务&#xff0c;为用户提供了一个方便、高效的方式来访问和操作存储在 Hive 中的数据。 1. Hive 查询服务&#xff08;HiveServer2&#xf…

STM32自己从零开始实操01:原理图

在听完老师关于 STM32 物联网项目的所有硬件课程之后&#xff0c;就是感觉自己云里雾里&#xff0c;明明课程都认真听完了&#xff0c;笔记也认真记录&#xff0c;但是就是感觉学到的知识还不是自己。 遂决定站在老师的肩膀上自己开始设计项目&#xff0c;将知识变成自己的&am…

沉浸式推理乐趣:体验线上剧本杀小程序的魅力

在这个信息爆炸的时代&#xff0c;人们的娱乐方式也在不断地推陈出新。其中&#xff0c;线上剧本杀小程序以其独特的沉浸式推理乐趣&#xff0c;成为了许多人的新宠。它不仅让我们在闲暇之余享受到了推理的快乐&#xff0c;更让我们在虚拟的世界里感受到了人性的复杂与多彩。 线…

【Linux网络编程】数据链路层

数据链路层 1.以太网帧格式2.重谈局域网转发的原理(基于协议)3.认识MTU3.1MTU对IP协议的影响3.2MTU对UDP协议的影响3.3MTU对于TCP协议的影响 4.ARP协议 点赞&#x1f44d;&#x1f44d;收藏&#x1f31f;&#x1f31f;关注&#x1f496;&#x1f496; 你的支持是对我最大的鼓励…

Windows系统下将MySQL数据库表内的数据全量导入Elasticsearch

目录 下载安装Logstash 配置Logstash配置文件 运行配置文件 查看导入结果 使用Logstash将sql数据导入Elasticsearch 下载安装Logstash 官网地址 选择Windows系统&#xff0c;需下载与安装的Elasticsearch相同版本的&#xff0c;下载完成后解压安装包。 配置Logstash配…

浏览器的同源策略与解决跨域

同源策略&#xff08;协议、域名、端口&#xff09; 同源策略&#xff08;Same-Origin Policy&#xff09;是一个在浏览器安全模型中被实施的重要安全机制。它是基于域名、协议和端口号的限制&#xff0c;用于防止不同源的网页间的恶意行为和信息泄露。 根据同源策略&#xf…