LeetCode刷题实战450:删除二叉搜索树中的节点
算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !
今天和大家聊的问题叫做 删除二叉搜索树中的节点,我们先来看题面:
https://leetcode-cn.com/problems/delete-node-in-a-bst/
Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST. Basically, the deletion can be divided into two stages: Search for a node to remove. If the node is found, delete the node.
给定一个二叉搜索树的根节点 root 和一个值 key,删除二叉搜索树中的 key 对应的节点,并保证二叉搜索树的性质不变。返回二叉搜索树(有可能被更新)的根节点的引用。
一般来说,删除节点可分为两个步骤:
首先找到需要删除的节点;
如果找到了,删除它。
示例
解题
https://blog.csdn.net/xxx_gt/article/details/103673563
首先是利用一个递归函数,每次排除1/2子树的节点,跟我上面的中序遍历相比,大大提高了效率。
递归函数,有两个要点要理解,一个是递归函数的作用,二是它返回的结果是什么。这道题里,这个递归函数的作用就是 删除一棵树里的目标节点,返回的是这棵修改后的树的根节点root。
递归过程:
deleteNode(root, key)
如果根节点的值大于目标节点key的值,说明key在左子树,所以递归调用(root.left, key)。key在左子树,也就说明 只用修改左子树就行了,右子树不用动,所以可以使 root.left = deleteNode(root.left, key).
如果根节点的值小于目标节点key的值,说明key在右子树,所以递归调用(root.right, key)。同理,rot.rght = deleteNode(root.right, key).
如果根节点的值等于目标节点key的值,说明找到key了,开始进行下一步处理。
(启示:说到 二叉搜索树BST时,不仅要想到中序遍历的结果是排好序的,还要想到可以递归,有点像二分查找的模式寻找目标值,提高效率)
删除节点:
经过上一步的递归过程,找到了key,而且key是要调整的这个子树的根节点。
(思考1:竟然不用存储pre节点,是怎么做到连接两个部分的树的?)
当遍历到这个节点时,其实变量名只是起到一个指针的作用,直接修改它的值就行,直接令它的值等于它的继承节点的值。
调整子树:
这部分用到两个子函数:
def successor(root): # 代表中序遍历序列的后一个节点,即比当前节点大的最小节点
root = root.right
while root.left:
root = root.left
return root.val
def predecessor(root): # 代表中序遍历序列的前一个节点,即比当前节点小的最大节点
root = root.left
while root.right:
root = root.right
return root.val
要分三种情况:
整个子树就只有一个节点,也就是根节点是叶节点,这是直接令其等于None就行了。
根节点有右子树,继承节点就选择 它的后一个节点(比目标节点大的最小节点)。
root.val = successor(root) # 用它的后继节点代替它
root.right = self.deleteNode(root.right, root.val) # 修改右子树
根节点无右子树但有左子树,继承节点就选择 它的前一个节点(比目标节点小的最大节点)。
root.val = predecessor(root) # 用它的后继节点代替它
root.left= self.deleteNode(root.left, root.val) # 修改右子树
代码如下:
class Solution:
def deleteNode(self, root: TreeNode, key: int) -> TreeNode:
if not root:
return None
def successor(root): # 代表中序遍历序列的下一个节点,即比当前节点大的最小节点
root = root.right
while root.left:
root = root.left
return root.val
def predecessor(root):
root = root.left
while root.right:
root = root.right
return root.val
if key > root.val: # 如果key大于根节点,则从右子树寻找
root.right = self.deleteNode(root.right, key)
elif key < root.val: # 如果key小于根节点,则从左子树寻找
root.left = self.deleteNode(root.left, key)
else: # key == 根节点
if not root.left and not root.right: # 如果根节点是叶节点,则直接删除该节点
return None
if root.right: # 如果该节点有右节点,则要找比它大的下一个节点(后继节点)
root.val = successor(root) # 用它的后继节点代替它
root.right = self.deleteNode(root.right, root.val)
else:
root.val = predecessor(root)
root.left = self.deleteNode(root.left, root.val)
return root
好了,今天的文章就到这里,如果觉得有所收获,请顺手点个在看或者转发吧,你们的支持是我最大的动力 。
上期推文:
相关文章
- 独家报道 lock.lock() 写在 try 外面?
- 中台之后,微服务是否也会被玩死?
- 高性能Nginx HTTPS调优!为HTTPS提速30%
- Go 命令行工具项目结构最佳实践
- Mattermost+Jira集成加速DevOps工作流程
- 开发者值得关注的9大流行PHP框架
- 谁再把IDEA的Project比作Eclipse的Workspace,我就跟谁急
- Consul实战:术语和命令解释
- 「平淡无奇小天才」:两块C++代码结合ASCII码,即可实现Nvidia光线追踪技术
- 探讨:Redux这么有名,只是我们不合适
- Github上看到的4个超级好玩的开源项目
- 前端开发者的现状:岂是一个乱字了得?
- 面试官问我 InnoDB 的物理存储结构!
- 十大经典排序算法详解之二希尔排序,归并排序,快速排序
- 如何从无序链表中移除重复项?有几种方式?
- 1 分钟带你认识从 "?" 到 "锟斤拷"
- 架构师必备:多维度查询的优秀实践
- 14 张有趣深动图解 FlexBox,还不快进收藏夹吃灰
- 这12个关于软件测试的误解,是时候澄清了
- 图数据科学助力精准预测,引领人工智能实现跨越发展