文档章节

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

o
 osc_w9s1w4o0
发布于 2019/04/02 07:06
字数 437
阅读 11
收藏 0
def

精选30+云产品,助力企业轻松上云!>>>

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

题意

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

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

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

  2. 如果找到了,删除它。

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

解题思路

  • 找到要删除的结点以后,将该结点的值替换成左子树中的最右子结点的值,并且将替换后的结点删除;

  • 和上面类似,只不过是被右子树中的最左子结点替换;

实现

class Solution(object):
   def deleteNode(self, root, key):
       """
      :type root: TreeNode
      :type key: int
      :rtype: TreeNode
      """
       if not root:
           return root
       
       # 从左子树中找
       if root.val > key:
           root.left = self.deleteNode(root.left, key)
# 从右子树中找
       elif root.val < key:
           root.right = self.deleteNode(root.right, key)
       else:
        # 判断是否左右子树是否都存在
           if not root.left:
               return root.right
           elif not root.right:
               return root.left
           else:
            # 找到左子树的最右子结点
               tmp = root.left
               while tmp.right:
                   tmp = tmp.right
               root.val = tmp.val
               # 删除左子树的最右子结点后,重构左子树
               root.left = self.deleteNode(root.left, tmp.val)
       return root
     
def deleteNode(self, root, key):
       """
      :type root: TreeNode
      :type key: int
      :rtype: TreeNode
      """
       if not root:
           return root
       
       if root.val > key:
           root.left = self.deleteNode(root.left, key)
           return root
       elif root.val < key:
           root.right = self.deleteNode(root.right, key)
           return root

       if not root.left:
           return root.right
       elif not root.right:
           return root.left
       
       tmp = self.findmin(root.right)
       tmp.right = self.delmin(root.right)
       tmp.left = root.left
       return tmp
   
   def findmin(self, root):
    """
    找到右子树中的最左子结点
    """
       if not root.left:
           return root
       return self.findmin(root.left)
   
   def delmin(self, root):
    """
    删除右子树中的最左子结点
    """
       if not root.left:
           return root.right
       
       root.left = self.delmin(root.left)
       return root

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
LeetCode刷题总结-树篇(中)

本篇接着《LeetCode刷题总结-树篇(上)》,讲解有关树的类型相关考点的习题,本期共收录17道题,1道简单题,10道中等题,6道困难题。 在LeetCode题库中,考察到的不同种类的树有七种,分别是...

osc_20n6g71c
2019/11/28
2
0
LeetCode刷题总结-树篇(中)

本篇接着《LeetCode刷题总结-树篇(上)》,讲解有关树的类型相关考点的习题,本期共收录17道题,1道简单题,10道中等题,6道困难题。 在LeetCode题库中,考察到的不同种类的树有七种,分别是...

舞动的心
2019/11/28
0
0
BST二分搜索树题目总结(都是很经典的递归)

Count of Smaller Numbers After Self 计算右侧小于当前元素的个数(逆序数) 图源:慕课网 1. 原始题目 计算右侧小于当前元素的个数 给定一个整数数组 nums,按要求返回一个新数组 counts。数...

osc_t2w0zvsf
2019/04/29
8
0
自己动手实现java数据结构(六)二叉搜索树

1.二叉搜索树介绍   前面我们已经介绍过了向量和链表。有序向量可以以二分查找的方式高效的查找特定元素,而缺点是插入删除的效率较低(需要整体移动内部元素);链表的优点在于插入,删除元...

小熊餐馆
2019/01/24
0
0
(算法总结)二叉排序树的节点删除(leetcode 450)

二叉排序树的节点插入和查找已经在本人的上一篇博文中讲解过了,大家可以参考: https://blog.csdn.net/little_fire/article/details/80798663 本篇博文将为大家重点讲解一下二叉排序树的节点...

奋斗的小炎
03/31
0
0

没有更多内容

加载失败,请刷新页面

加载更多

asp.net core之NLog

NuGet添加 NLog.Web.AspNetCore。 <PackageReference Include="Microsoft.AspNetCore.App" /> 添加配置文件 新建一个文件nlog.config(建议全部小写,linux系统中要注意), 并右键点击其属性......

一介草民Coder
19分钟前
23
0
.NET中的struct和class有什么区别? - What's the difference between struct and class in .NET?

问题: .NET中的struct和class有什么区别? 解决方案: 参考一: https://stackoom.com/question/3OT/NET中的struct和class有什么区别 参考二: https://oldbug.net/q/3OT/What-s-the-differ...

富含淀粉
今天
23
0
android:layout_weight是什么意思? - What does android:layout_weight mean?

问题: I don't understand how to use this attribute. 我不明白如何使用这个属性。 Can anyone tell me more about it? 谁能告诉我更多关于它的事情? 解决方案: 参考一: https://stacko...

javail
今天
17
0
CSS背景不透明度[重复] - CSS Background Opacity [duplicate]

问题: This question already has an answer here: 这个问题已经在这里有了答案: How do I give text or an image a transparent background using CSS? 如何使用CSS为文本或图像提供透明背...

fyin1314
今天
31
0
node http 获取gb2312网页如何转为utf8

最初,我想当然认为是下述做法,但被证明是错误的 const http = require('http'), iconv = require('iconv-lite');const url = 'http://xxx';http.get(url, function(res) { var bo......

高延
今天
24
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部