0
  • 聊天消息
  • 系统消息
  • 评论与回复
登录后你可以
  • 下载海量资料
  • 学习在线课程
  • 观看威廉希尔官方网站 视频
  • 写文章/发帖/加入社区
会员中心
创作中心

完善资料让更多小伙伴认识你,还能领取20积分哦,立即完善>

3天内不再提示

删除二叉搜索树中的节点

算法与数据结构 来源:五分钟学算法 2020-06-23 10:33 次阅读

今天分享的题目来源于 LeetCode 第 450 号问题:删除二叉搜索树中的节点。虽然它的难度是中等,但实际上很好理解,请往下看!

题目描述

给定一个二叉搜索树的根节点root和一个值key,删除二叉搜索树中的key对应的节点,并保证二叉搜索树的性质不变。返回二叉搜索树(有可能被更新)的根节点的引用。

一般来说,删除节点可分为两个步骤:

首先找到需要删除的节点;

如果找到了,删除它。

说明:要求算法时间复杂度为 O(h),h 为树的高度。

示例:

root=[5,3,6,2,4,null,7] key=3 5 / 36 / 247 给定需要删除的节点值是3,所以我们首先找到3这个节点,然后删除它。 一个正确的答案是[5,4,6,2,null,null,7], 如下图所示。 5 / 46 / 27 另一个正确答案是[5,2,6,null,4,null,7]。 5 / 26 47

题目解析

在二叉搜索树上删除一个节点,这道题目有一个隐含的条件,就是树上节点的值不重复。

另外题目还要求时间复杂度需要保证 O(h) 这里的 h 表示的是二叉树的高度。

其实这个题目是分成两个步骤的,第一个是找到对应的节点,第二个是删除节点。

因为是二叉搜索树,对于树上每个节点来说,其右子树的节点都要大于其左子树的节点,那么要找对应节点,我们可以从根节点开始,一路比较,大的话就去右边找,小的话就去左边找,这样每次我们都往下,可以保证时间复杂度是 O(h)。

当我们找到了要删除的节点,在删除这一步就会有很多的细节,主要是因为我们需要调整余下的结构,以维持二叉搜索树的性质。

针对这个问题,我们可以分情况讨论:

5 / 36 / 247 / 18

情况 1:当删除的节点没有左右子树,比如上图的 4、8、1
这时直接删除即可,树依旧可以保持二叉搜索树的性质

情况 2:当删除的节点有左子树没有右子树,比如上图的 2
这时我们只需要将整个左子树移到当前位置即可
也就是将左子树的根节点放到删除节点的位置,其余不变

情况 3:当删除的节点没有左子树有右子树,比如上图的 6、7
这时我们只需要将整个右子树移到当前位置即可
也就是将右子树的根节点放到删除节点的位置,其余不变

情况 4:当删除的节点既有左子树又有右子树,比如上图的 5、3
这时就有两种方法供选择:
去到左子树中,找到值最大节点,将右子树全部移到这个节点下
去到右子树中,找到值最小节点,将左子树全部移到这个节点下

通过上面的讨论分析,我们有了大致的思路。在实现方面,我们可以借助递归来巧妙地达到删除对应节点的目的。

图片描述

参考代码

//五分钟学算法 publicTreeNodedeleteNode(TreeNoderoot,intkey){ if(root==null){ returnnull; } //当前遍历到的节点大于要找的节点,去左边继续找 if(root.val>key){ root.left=deleteNode(root.left,key); } //当前遍历到的节点小于要找的节点,去右边继续找 elseif(root.val< key) {         root.right = deleteNode(root.right, key);     }      // 找到要删除的节点,进行删除操作     else {         // 情况 1 & 2         if (root.right == null) {             return root.left;         }          // 情况 3         if (root.left == null) {             return root.right;         }         // 去到删除节点的右子树,找到值最小的节点         TreeNode rightSmallest = root.right;         while (rightSmallest.left != null) {             rightSmallest = rightSmallest.left;         }         // 将删除节点的左子树全部移到这个节点下         rightSmallest.left = root.left;         // 返回右子树的根节点,放到当前删除节点的位置         return root.right;     }     return root; }

声明:本文内容及配图由入驻作者撰写或者入驻合作网站授权转载。文章观点仅代表作者本人,不代表电子发烧友网立场。文章及其配图仅供工程师学习之用,如有内容侵权或者其他违规问题,请联系本站处理。 举报投诉
  • 算法
    +关注

    关注

    23

    文章

    4608

    浏览量

    92855
  • 二叉树
    +关注

    关注

    0

    文章

    74

    浏览量

    12324

原文标题:五分钟看懂一道中等难度的算法题

文章出处:【微信号:TheAlgorithm,微信公众号:算法与数据结构】欢迎添加关注!文章转载请注明出处。

收藏 人收藏

    评论

    相关推荐

    谷歌取消“站点链接搜索框”,适应新搜索需求

    近日,谷歌发布了一则通知,决定取消搜索结果的“站点链接搜索框”。这一功能已经陪伴了用户十多年,它允许用户在特定网站上进行更深入的搜索,为许多网民提供了便利。然而,随着时代的变迁和威廉希尔官方网站
    的头像 发表于 10-23 11:20 334次阅读

    逻辑组件的流程块节点通常出于什么用途

    逻辑组件的流程块节点是流程图、状态图、序列图等图表的基本元素,它们用于表示业务流程、工作流程、算法步骤、系统状态等。这些节点在软件开发、项目管理、自动化控制、工程设计、科学研究等领
    的头像 发表于 10-15 14:38 154次阅读

    什么是默克尔(Merkle Tree)?如何计算默克尔根?

    01 默克尔的概念 默克尔(Merkle Tree)是一种特殊的二叉树,它的每个节点都存储了一个数据块的哈希值。哈希值是一种可以将任意长度的数据转换为固定长度的字符串的算法,它具有
    的头像 发表于 09-30 18:22 857次阅读
    什么是默克尔<b class='flag-5'>树</b>(Merkle Tree)?如何计算默克尔根?

    ubuntu删除的文件怎么恢复

    在Ubuntu系统删除的文件可以通过多种方法进行恢复。本文将详细介绍Ubuntu系统删除文件的恢复方法,包括使用命令行工具、文件恢复软件以及预防文件丢失的策略。本文将分为以下几个
    的头像 发表于 08-30 15:10 1404次阅读

    节点电压法流入节点电流怎么判断正负

    节点电压法(Node Voltage Method)是一种在电路分析中常用的方法,用于求解电路节点的电压。在这种方法,我们通常选择一个参考节点
    的头像 发表于 08-06 17:24 2116次阅读

    节点电压法的实质是什么

    节点电压法(Node Voltage Method)是一种在电路分析中常用的方法,主要用于求解线性电路的电压和电流。它基于基尔霍夫电流定律(KCL)和欧姆定律,通过建立节点电压方程来求解电路
    的头像 发表于 08-06 17:08 949次阅读

    修改“u-boot”设备的电源后,使用\"STM32CubeProgrammer\"下载会一直重复下载,为什么?

    我自己做的板子电源部分没有使用\"stpmic\",而是使用分立式电源,我在移植OpenSTLinux(5.1.0)时遇到了问题,我修改“u-boot”设备的电源后
    发表于 07-23 07:57

    节点电压法电压源怎么处理

    节点电压法(Node Voltage Method,简称NVM)是电路分析的一种基本方法,主要应用于求解线性电路节点电压。在节点电压法
    的头像 发表于 07-12 09:20 2915次阅读

    mesh的非叶子节点是如何配置的?

    mesh的非叶子节点是如何配置的?是mesh网络自动生成吗?
    发表于 07-11 08:28

    指电极上覆盖敏感材料的阻值计算

    覆盖的敏感材料厚度超出指厚度时计算电阻,是否可以视作指电极指间电阻多个周期串联后与超出指厚度部分敏感材料电阻并联
    发表于 07-05 14:48

    什么是工业控制网络节点?常用的节点有哪些

    工业控制网络节点是指在工业控制网络,用于实现数据采集、处理、传输和控制等功能的设备。它们是工业控制系统的重要组成部分,对于保证工业生产的稳定性、可靠性和高效性具有重要意义。 一、工业控制网络
    的头像 发表于 06-11 10:36 1099次阅读

    服务器数据恢复—存储卷被删除后重建如何恢复被删除卷的数据?

    服务器存储数据恢复环境: 某品牌FlexStorage P5730服务器存储,存储中有一组由24块硬盘组建的RAID5阵列,包括1块热备硬盘。 服务器存储故障: 存储的2个卷被删除删除之后重建了一个新卷。需要恢复之
    的头像 发表于 06-05 11:03 649次阅读

    谷歌Play商店强制推行应用账户删除政策

     如今,该新规已正式施行,Google将开始在应用详情展示删除账户方式。Android Authority报道指出,“账户可删除”标识已出现在应用数据安全部分。
    的头像 发表于 05-27 17:49 1194次阅读

    Windows驱动器分区可以删除

    可以删除Windows驱动器分区。删除驱动器分区的操作可以在Windows操作系统的磁盘管理工具完成。然而,在执行此操作之前,请务必提前备份重要的数据,以免丢失。 以下是
    的头像 发表于 02-14 17:00 1485次阅读

    语音数据集在智能语音搜索的应用与挑战

    挥着重要作用,为系统提供了丰富的语音数据和信息,提高了搜索的准确性和效率。本文将详细介绍语音数据集在智能语音搜索的应用、面临的挑战以及未来的发展趋势。 、语音数据集在智能语音
    的头像 发表于 01-18 15:09 549次阅读