第二十四天 | 501.二叉搜索树中的插入操作 450.删除二叉搜索树中的节点

题目:501.二叉搜索树中的插入操作

自己有一定的思路,但是遇到的难点:

        可以找到val应该插入的位置,但如何建立新节点的结构呢?也就是说新建立的node应该怎么指,是搭建左孩子还是右孩子?又是应该被pre所指还是被root所指呢?

写出了如下代码:

class Solution {
public:TreeNode *pre = NULL;TreeNode* insertIntoBST(TreeNode* root, int val) {if(root == NULL) return NULL;TreeNode *left = insertIntoBST(root->left, val);if(pre == NULL){if(root->val > val){TreeNode *node = new TreeNode(val);root->left = node;return root;}else{pre = root;}}else{if(root->val > val && pre->val < val){TreeNode *node = new TreeNode(val);root->left = node;return root;}else{pre = root;}}TreeNode *right = insertIntoBST(root->right, val);if(left != NULL && right == NULL) return left;if(left == NULL && right != NULL) return right;return NULL;}
};

本题最简单的思路:

        不用考虑题干所说改变二叉树结构、插入位置有多种情况那么复杂,将所插入的值都插入在最底层,即最底层一定可以找到满足条件的位置。

        按照二叉树的特性进行向下搜索递归,一直到最低点,此时建立新节点,并将建立的节点返回,这是终止条件。

        对于单层递归逻辑,应该如所示进行判断,按照大小进行搜索,每一层将节点返回。

有一个难以理解的地方,返回的节点应该用什么接住?

        此时可以用最底层的返回值来模拟一下:新建立的节点被返回了,应该接在上一层的root->left或者root->right,即返回给root->left或者root->right。

代码如下:

class Solution {
public:TreeNode* insertIntoBST(TreeNode* root, int val) {if(root == NULL){TreeNode *node = new TreeNode(val);return node;}if(root->val > val){root->left = insertIntoBST(root->left, val);return root;}if(root->val < val){root->right = insertIntoBST(root->right, val);return root;}return root;}
};

可看出本题的遍历顺序其实不属于前、中或者后,而是根据搜索二叉树的特性向下搜索到目标位置。

450.删除二叉搜索树中的节点(难)

删除节点要考虑五种情况:

        1.没有找到需要删除的节点。

        2.需要删除的节点是叶子节点,左为空右也为空。

        3.需要删除的节点,其左不为空右为空。

        4.需要删除的节点,其左为空右不为空。

        5.需要删除的节点其左右都不为空。(此种情况最难,需要大幅改动二叉树结构)

终止条件比较复杂(因为删除节点的操作就在终止条件里):

        ①如果遍历到NULL,说明本条路径没有找到目标节点,返回 NULL

        如果找到需要删除的节点(key):

                ②判断是不是叶子节点。return NULL,一定要理解为什么要return NULL?其实是将NULL返回给上一层的子树。

                ③如果左不为空右为空,返回该节点的子树,同样的,该节点的子树返回给了哪里?答:赋值给了上一层。

                ④左为空右不为空同理。

               ⑤左右都不为空:要找到最接近待删除节点那个数的数(比key大一点点或小一点点任选其一),定义一个cur作为指针去遍历到最接近待删除节点那个数的数,然后改动树的结构(详见代码)。最后记得释放内存。

单层递归逻辑:

        利用二叉树的特性,向下遍历,注意递归的返回值要用什么接住?

注意:在自己写代码时很容易在最最最后,即单层递归之后忘写返回值,有时也不知道该返回什么。像本题就应该返回root(其实我个人理解,在出第一层之外之不可能执行最后这个return的,必定都会在上面的语句中都返回了。这一句话主要是为了保证第一层函数有返回值,就是说执行完所有的递归完成了删除节点的操作后,会将新二叉树的根节点返回。不然会报错:这个函数没有返回值)(前面说的有问题,每一层递归(除了判断终止条件的时候)都会执行这个return语句,将重新构造的树的root返回给上一层)

class Solution {
public:TreeNode* deleteNode(TreeNode* root, int key) {if(root == NULL) return NULL; // 第一种情况:没找到删除的节点,遍历到空节点直接返回了if(root->val == key){// 第二种情况:左右孩子都为空(叶子节点),直接删除节点, 返回NULL为根节点if(root->left == NULL && root->right == NULL){delete root;return NULL;}// 第三种情况:其左孩子不为空,右孩子为空,删除节点,右孩子补位 ,返回右孩子为根节点else if(root->left != NULL && root->right == NULL){auto retNode = root->left;delete root;return retNode;}// 第三种情况:其左孩子为空,右孩子不为空,删除节点,右孩子补位 ,返回右孩子为根节点else if(root->left == NULL && root->right != NULL){auto retNode = root->right;delete root;return retNode;}// 第五种情况:左右孩子节点都不为空,则将删除节点的左子树放到删除节点的右子树的最左面节点的左孩子的位置// 并返回删除节点右孩子为新的根节点。else{TreeNode *cur = root->right;          //现在要将root删除,企图将root->left接在右子树的下面while(cur->left) cur = cur->left;     //如果cur->left还存在,说明此时cur还不是比root大且理root最近的节点cur->left = root->left;       // 把要删除的节点(root)左子树放在cur的左孩子的位置TreeNode *tmp = root;      // 把root节点保存一下,下面来删除root = root->right;        // 返回旧root的右孩子作为新rootdelete tmp;                // 释放节点内存(这里不写也可以,但C++最好手动释放一下吧)return root;}}if(root->val > key) root->left = deleteNode(root->left, key);    //deleteNode函数有返回值,其返回值需要用root->left接住if(root->val < key) root->right = deleteNode(root->right, key);return root;}
};

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

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

指标体系建设方案(36页PPT)

一、资料介绍 《指标体系建设方案》这份36页的PPT资料包&#xff0c;是针对当前组织发展需求而精心设计的一套全面、系统的指标构建方案。本资料包从理论到实践&#xff0c;深入浅出地阐述了指标体系建设的必要性、原则、步骤及实施要点&#xff0c;旨在帮助组织建立起科学、合…

人工智能到底是什么玩意儿?

说实话&#xff0c;每次听到“人工智能”这个词&#xff0c;我都感觉像是在听天书一样。它似乎总是被包裹在一堆高大上的术语和概念里&#xff0c;让人摸不着头脑。但今天&#xff0c;我决定挑战一下自己&#xff0c;把这个问题搞个明白&#xff01; 首先&#xff0c;我得承认&…

selenium发展史

Selenium Core 2004 年&#xff0c;Thoughtworks 的工程师 Jason Huggins 正在负责一个 Web 应用的测试工作&#xff0c;由于这个项目需要频繁回归&#xff0c;这导致他不得不每天做着重复且低效的工作。为了解决这个困境&#xff0c;Jason 开发了一个运行在 JavaScript 沙箱中…

Dockerfile中yum install 无法使用的问题

记录一次开发中使用Dockerfile进行centos7容器自定义的时候发现yum install无法使用 1. 查看主机是否能够联网 ping www.baidu.com主机能够联网 2. 查看进行Dockerfile进行打包的时候新容器是否联网 在Dockerfile中添加 RUN ping www.baidu.com 发现无法ping通 解决办法 …

节点电位与电路电压的研究

实验目的&#xff1a; 1. 验证电路中电位与电压的关系&#xff1b; 2. 掌握电路电位图的绘制方法&#xff1b; 3. 学会对简单的电路故障进行分析与排除。 实验内容及步骤&#xff1a; 1. 从“线性电路研究模块”实验板上选取元器件&#xff0c;结合实验箱提供的电源&#xff…

位拆分与运算

描述 题目描述&#xff1a; 现在输入了一个压缩的16位数据&#xff0c;其实际上包含了四个数据[3:0][7:4][11:8][15:12], 现在请按照sel选择输出四个数据的相加结果,并输出valid_out信号&#xff08;在不输出时候拉低&#xff09; 0: 不输出且只有此时的输入有…

EasyClick常见拓展函数及应用

十天学会从入门到实战游戏脚本开发教程--EassyClick入门教程&#xff1a;2024 十天学会EasyClick从入门到实战&#xff0c;自动化脚本&#xff0c;游戏脚本开发系列教程_哔哩哔哩_bilibili2024 十天学会EasyClick从入门到实战&#xff0c;自动化脚本&#xff0c;游戏脚本开发系…

Redis-Redis事务

Redis事务 Redis事务简介 Redis事务是一组命令的集合&#xff0c;一个事务中的所有命令都将被序列化&#xff0c;按照一次性、顺序性、排他 性的执行队列系列的命令。Redis单条命令保证原子性&#xff0c;但是事务不保证原子性&#xff0c;且没有回滚。事务中任意命令执行失败…

DBeaver如何csv导入数据

简言之先要创建任务&#xff0c;任务还需要去执行&#xff0c;只有执行之后才是执行真的导入了 那个保存任务真的很误导人啊 1.首先点击你要被导入的表&#xff0c;右键选择导入数据然后选择直接点击下一步,这个地方需要修改格式&#xff0c;否则会乱码 如果你导入的没有标题…

GPT-4o API 全新版本发布:提升性能,增加性价比

5月13日&#xff0c;OpenAI 发布了全新ChatGPT模型 GPT-4o&#xff0c;它在响应速度和多媒体理解上都有显著提升。在这篇文章中&#xff0c;我们将介绍 GPT-4o 的主要特点及其 API 集成方式。 什么是 GPT-4o&#xff1f; GPT-4o 是 OpenAI 于5月13日发布的最新多模态 AI 模型…

职业生涯第一课---“Redis分布式锁优化:确保唯一性与效率“

前言 最近因为刚入职公司开启自己的实习生涯&#xff0c;工作和毕设论文同步进行&#xff0c;导致有段时间没更新博客了&#xff0c;今天来分享一下最近学到的一些知识。 场景介绍 BOSS让我写一些接口&#xff0c;他提出这样一个需求&#xff0c;该接口的参数有多个&#xf…

ubuntu下不生成core dumped

1、先用ulimit -c&#xff0c;如果看到0&#xff0c;说明没有开core dump。 所以我们输入ulimit -c unlimited&#xff0c;打开core dump。 再次用ulimit -c&#xff0c;看到unlimited了&#xff0c;说明core dump打开了。 注意这句ulimit -c unlimited只对当前会话有效。要永…

酷开科技的智能电视操作系统—酷开系统,带来更加舒适的观看体验

酷开科技的智能电视操作系统——酷开系统&#xff0c;通过大数据和人工智能技术的结合&#xff0c;会根据会员的观看历史和收视行为偏好&#xff0c;刻画出“消费者群体画像”&#xff0c;然后将内容进行“人工编辑智能推荐”的方式推送到消费者面前&#xff0c;不仅省去了消费…

在Python中防止某些字段被Pickle序列化

在Python中&#xff0c;如果你想防止某些字段被pickle序列化&#xff0c;可以使用__reduce__()方法来自定义pickle行为。__reduce__()方法允许你返回一个元组&#xff0c;其中包含要在对象被pickle时调用的函数以及传递给该函数的参数。下面就是我遇到的问题以及最终解决方案。…

Verdaccio私服搭建

前言 Verdaccio是一个轻量级的私有npm注册表&#xff0c;由Node.js创建&#xff0c;并且是sinopia1.4.0的衍生版本&#xff0c;与其100%向后兼容。Verdaccio的名称来源于意大利中世纪晚期fresco绘画中流行的一种绿色。 Verdaccio的主要功能是在本地环境中管理和共享npm软件包。…

鸿蒙应用开发之调用C++开发代码库3

接着下来,我们仔细分析C++代码的实现,要理解怎么样把ArkTS类型转换为C++类型,并且返回参数值时,怎么从C++的类型转换为ArkTS类型。 要想在ArkTS调用C++的代码,需要把上面的编译器信息打包到应用程序HAP里,当运行的时候,就可以找到加载的对应的声明信息。 我们从JS调用框…

framework ‘CoreAudioTypes‘ not found

几天前我升级Xcode15之后遇到了这个问题。关于“CoreAudioTypes”的信息完全是误导。在我的例子中&#xff0c;原因是在删除一些旧代码时&#xff0c;我不小心删除了仍然需要的类。然而&#xff0c;在构建时弹出的唯一消息是关于“CoreAudioTypes”——当我恢复丢失的类时&…

基于区块链的Web 3.0关键技术研讨会顺利召开

基于区块链的Web3.0关键技术研讨会 2024年4月23日&#xff0c;由国家区块链技术创新中心主办的“基于区块链的web3.0关键技术研讨会”召开。Web3.0被用来描述一个运行在“区块链”技术之上的“去中心化”的互联网&#xff0c;该网络上的主体掌握自己数据所有权和使用权&#xf…

使用OpenCV GUI清理数据集 | 为目标检测模型创建更好的数据集

点击下方卡片&#xff0c;关注“小白玩转Python”公众号 在深度学习中有几件重要的事情&#xff0c;我认为数据是最关键的。如果没有合适的数据&#xff0c;要取得好的结果是非常困难的。即使你用强大的预训练模型和GPU训练模型&#xff0c;你的模型也可能表现不佳。在本文中&a…

Kotlin核心编程知识点-02-面向对象

文章目录 1.类和构造方法1.1.Kotlin 中的类及接口1.1.1.Kotlin 中的类1.1.2.可带有属性和默认方法的接口 1.2.更简洁地构造类的对象1.2.1.构造方法默认参数1.2.2.init 语句块1.2.3.延迟初始化&#xff1a;by lazy 和 lateinit 1.3.主从构造方法 2.不同的访问控制原则2.1.限制修…