当前位置:网站首页>leetcode刷题:二叉树27(删除二叉搜索树中的节点)
leetcode刷题:二叉树27(删除二叉搜索树中的节点)
2022-07-07 10:30:00 【涛涛英语学不进去】
450.删除二叉搜索树中的节点
给定一个二叉搜索树的根节点 root 和一个值 key,删除二叉搜索树中的 key 对应的节点,并保证二叉搜索树的性质不变。返回二叉搜索树(有可能被更新)的根节点的引用。
一般来说,删除节点可分为两个步骤:
首先找到需要删除的节点;
如果找到了,删除它。
说明: 要求算法时间复杂度为 O ( h ) O(h) O(h),h 为树的高度。
示例:
思路
搜索树的节点删除要比节点增加复杂的多,有很多情况需要考虑,做好心里准备。
这题不难,五小时就做完了。不想写题解。细心模拟,多跟着图走,一定要画图。
package com.programmercarl.tree;
import com.programmercarl.util.GenerateTreeNode;
/** * @ClassName DeleteNode * @Descriotion TODO * @Author nitaotao * @Date 2022/7/6 15:08 * @Version 1.0 * https://leetcode.cn/problems/delete-node-in-a-bst/ * 450. 删除二叉搜索树中的节点 **/
public class DeleteNode {
public static void main(String[] args) {
System.out.println(new Traversal().inorderTraversal(
new DeleteNode().deleteNode(GenerateTreeNode.generateTreeNode("[2,0,33,null,1,25,40,null,null,11,31,34,45,10,18,29,32,null,36,43,46,4,null,12,24,26,30,null,null,35,39,42,44,null,48,3,9,null,14,22,null,null,27,null,null,null,null,38,null,41,null,null,null,47,49,null,null,5,null,13,15,21,23,null,28,37,null,null,null,null,null,null,null,null,8,null,null,null,17,19,null,null,null,null,null,null,null,7,null,16,null,null,20,6]"), 33)
));
}
public TreeNode deleteNode(TreeNode root, int key) {
if (root == null) {
//当前值的结点不存在
return null;
}
if (root.val == key) {
// 父结点不存在
if (root.left != null && root.right == null) {
return root.left;
}
if (root.left == null && root.right != null) {
return root.right;
}
//只有一个结点
if (root.left == null && root.right == null) {
return null;
}
//剩下的情况就是左右结点均存在了
TreeNode left = root.left;
TreeNode right = root.right;
if (root.right.left == null) {
//如果右子节点的左边不存在
// 则直接右子节点的左边为左子节点
root.right.left = left;
//返回头结点 右子节点
return root.right;
} else if (root.left.right == null) {
//如果左子节点的右边不存在
// 则直接左子节点的右边为右子节点
root.left.right = right;
//返回头结点 右子节点
return root.left;
} else {
//如果左右子树都有自己的左右子树
//就让左子树的最右下子节点替换root的值即可
TreeNode leftRightNode = left.right;
while (leftRightNode.right != null) {
left = left.right;
leftRightNode = leftRightNode.right;
}
//此时leftRightNode为最右下角子节点
int value = leftRightNode.val;
//删除最右下角结点
left.right = null;
root.val = value;
return root;
}
}
TreeNode rootNode = root;
parentNode = root;
findNode(rootNode, key, false);
return root;
}
TreeNode parentNode;
public TreeNode findNode(TreeNode root, int key, boolean isLeft) {
if (root == null) {
//当前值的结点不存在
return null;
}
if (root.val > key) {
parentNode = root;
findNode(root.left, key, true);
} else if (root.val < key) {
parentNode = root;
findNode(root.right, key, false);
} else {
//找到值
// root.val == key
// root 可能有老有小
// 父结点 左子节点 右子节点
//如果父结点存在
if (root.left != null && root.right == null) {
//当前结点左结点存在,右结点不存在
//当前结点是父结点的左子节点,即父节点比当前结点大
if (isLeft) {
parentNode.left = root.left;
} else {
// 如果当前结点是父结点的右子节点,即父节点比当前结点小
parentNode.right = root.left;
}
return null;
}
if (root.left == null && root.right != null) {
//当前结点左结点不存在,右结点存在
//当前结点是父结点的左子节点,即父节点比当前结点大
if (isLeft) {
parentNode.left = root.right;
} else {
// 如果当前结点是父结点的右子节点,即父节点比当前结点小
parentNode.right = root.right;
}
return null;
}
if (root.left == null && root.right == null) {
//如果当前结点是叶子结点
if (isLeft) {
parentNode.left = null;
} else {
parentNode.right = null;
}
return null;
}
//左右父结点均存在
// 如果当前结点是父结点的左结点
// 即当前结点比父结点小
if (isLeft) {
//如果左右子树都有自己的左右子树
//找右子树最左下角的元素替代自己
if (root.left == null && root.right == null) {
parentNode.left = null;
} else if (root.left == null && root.right != null) {
parentNode.left = root.right;
} else {
//左 右 都不为空
if (root.left.right == null) {
parentNode.left = root.left;
root.left.right = root.right;
} else {
//左子树右下角不为空
TreeNode left = root.left;
TreeNode leftRightNode = left.right;
while (leftRightNode.right != null) {
left = left.right;
leftRightNode = leftRightNode.right;
}
int value = leftRightNode.val;
if (leftRightNode.left != null) {
left.right = leftRightNode.left;
} else {
left.right = null;
}
root.val = value;
return root;
}
}
return root;
} else {
//如果左右子树都有自己的左右子树
//找左子树最右下角的元素替代自己
if (root.left == null && root.right == null) {
parentNode.right = null;
} else if (root.right == null && root.left != null) {
parentNode.right = root.left;
} else {
//左 右 都不为空
if (root.right.left == null) {
parentNode.right = root.right;
root.right.left = root.left;
} else {
//右子树左下角不为空
TreeNode right = root.right;
TreeNode rightRightNode = right.left;
while (rightRightNode.left != null) {
right = right.left;
rightRightNode = rightRightNode.left;
}
int value = rightRightNode.val;
if (rightRightNode.right != null) {
right.left = rightRightNode.right;
} else {
right.left = null;
}
root.val = value;
return root;
}
}
return root;
}
}
return null;
}
}
边栏推荐
- 如何理解服装产业链及供应链
- ES底层原理之倒排索引
- Solutions to cross domain problems
- 111. Network security penetration test - [privilege escalation 9] - [windows 2008 R2 kernel overflow privilege escalation]
- OSPF exercise Report
- Utiliser la pile pour convertir le binaire en décimal
- 普乐蛙小型5d电影设备|5d电影动感电影体验馆|VR景区影院设备
- Completion report of communication software development and Application
- Configure an encrypted web server
- The hoisting of the upper cylinder of the steel containment of the world's first reactor "linglong-1" reactor building was successful
猜你喜欢
Learning and using vscode
【统计学习方法】学习笔记——支持向量机(上)
The left-hand side of an assignment expression may not be an optional property access.ts(2779)
Unity map auto match material tool map auto add to shader tool shader match map tool map made by substance painter auto match shader tool
跨域问题解决方案
ES底层原理之倒排索引
Idea 2021 Chinese garbled code
[play RT thread] RT thread Studio - key control motor forward and reverse rotation, buzzer
In the small skin panel, use CMD to enter the MySQL command, including the MySQL error unknown variable 'secure_ file_ Priv 'solution (super detailed)
【PyTorch实战】用RNN写诗
随机推荐
数据库系统原理与应用教程(007)—— 数据库相关概念
30. Few-shot Named Entity Recognition with Self-describing Networks 阅读笔记
【统计学习方法】学习笔记——支持向量机(下)
About sqli lab less-15 using or instead of and parsing
Typescript interface inheritance
BGP actual network configuration
SQL lab 11~20 summary (subsequent continuous update) contains the solution that Firefox can't catch local packages after 18 levels
数据库系统原理与应用教程(009)—— 概念模型与数据模型
Is it safe to open Huatai's account in kainiu in 2022?
【统计学习方法】学习笔记——提升方法
The road to success in R & D efficiency of 1000 person Internet companies
Unity map auto match material tool map auto add to shader tool shader match map tool map made by substance painter auto match shader tool
Simple network configuration for equipment management
(待会删)yyds,付费搞来的学术资源,请低调使用!
@What happens if bean and @component are used on the same class?
[play RT thread] RT thread Studio - key control motor forward and reverse rotation, buzzer
VSCode的学习使用
Visual studio 2019 (localdb) \mssqllocaldb SQL Server 2014 database version is 852 and cannot be opened. This server supports version 782 and earlier
<No. 9> 1805. Number of different integers in the string (simple)
Dialogue with Wang Wenyu, co-founder of ppio: integrate edge computing resources and explore more audio and video service scenarios