leetcode 450. Delete Node in a BST 删除二叉搜索树中的节点 (中等)
一、题目大意
给定一个二叉搜索树的根节点 root 和一个值 key,删除二叉搜索树中的 key 对应的节点,并保证二叉搜索树的性质不变。返回二叉搜索树(有可能被更新)的根节点的引用。
一般来说,删除节点可分为两个步骤:
-
首先找到需要删除的节点;
-
如果找到了,删除它。
示例 1:
输入:root = [5,3,6,2,4,null,7], key = 3
输出:[5,4,6,2,null,null,7]
解释:给定需要删除的节点值是 3,所以我们首先找到 3 这个节点,然后删除它。
一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。
另一个正确答案是 [5,2,6,null,4,null,7]。
示例 2:
输入: root = [5,3,6,2,4,null,7], key = 0
输出: [5,3,6,2,4,null,7]
解释: 二叉树不包含值为 0 的节点
示例 3:
输入: root = [], key = 0
输出: []
提示:
-
节点数的范围 [0, 104].
-
-105 <= Node.val <= 105
-
节点值唯一
-
root 是合法的二叉搜索树
-
-105 <= key <= 105
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/delete-node-in-a-bst
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
二、解题思路
这道题让我们删除二叉搜索树中的一个节点,难点在于删除完节点并补上那个节点的位置后还应该是一棵二叉搜索树。被删除掉的节点位置,不一定是由其左右节点补上,
7
/ \
4 8
/ \
2 6
\ /
3 5
上面这棵树,如果要删除节点4,那么应该将节点5补到4的位置,这样才能保证还是BST,结果是下面这棵树
7
/ \
5 8
/ \
2 6
\
3
递归思路:首先判断根节点是否为空,由于BST的性质:左 < 根 < 右,使得可以快速定位到要删除的节点,对于当前节点值不等于key的情况,根据大小关系对其左右子节点分别调用递归函数。若当前节点就是要删除的节点,先判断若有一个子节点不存在,就将root指向另一个节点,如果左右节点都不存在,那么root就赋值为空了,也正确。难点就在于处理左右子节点都存在的情况,需要在右子树找到最濉址,即右子树中最左下方的节点,然后将该最小值赋值给root,然后再在右子树中调用递归函数来mbmw这个最小的节点。
三、解题方法
3.1 Java实现
public class Solution {
public TreeNode deleteNode(TreeNode root, int key) {
if (root == null) {
return null;
}
if (root.val > key) {
root.left = deleteNode(root.left, key);
} else if (root.val < key) {
root.right = deleteNode(root.right, key);
} else {
if (root.left == null || root.right == null) {
root = (root.left != null) ? root.left : root.right;
} else {
TreeNode cur = root.right;
while (cur.left != null) {
cur = cur.left;
}
root.val = cur.val;
root.right = deleteNode(root.right, cur.val);
}
}
return root;
}
}
四、总结小记
- 2022/10/21 脑力劳动的人更容易摸鱼
相关文章
- Leetcode: Max Consecutive Ones II(unsolved locked problem)
- Leetcode: Construct Binary Tree from Preorder and Inorder Traversal
- LeetCode Decode Ways
- LeetCode高频题15:三数之和
- JS Leetcode 33. 搜索旋转排序数组题解,图解旋转数组中的二分法
- JS leetcode 搜索插入位置 题解分析
- 150、【动态规划】leetcode ——96. 不同的二叉搜索树(C++版本)
- 【LeetCode】69. Sqrt(x) (2 solutions)
- leetcode先刷_Pascal's Triangle II
- [LeetCode] 1027. Longest Arithmetic Subsequence 最长的等差数列
- [LeetCode] 957. Prison Cells After N Days N天后的牢房
- [LeetCode] 869. Reordered Power of 2 重新排序为2的倍数
- [LeetCode] Minimum Distance Between BST Nodes 二叉搜索树中结点的最小距离
- [LeetCode] 428. Serialize and Deserialize N-ary Tree N叉搜索树的序列化和去序列化
- [LeetCode] Insert into a Binary Search Tree 二叉搜索树中插入结点
- [LeetCode] Search in a Binary Search Tree 二叉搜索树中搜索
- [LeetCode] Two Sum IV - Input is a BST 两数之和之四 - 输入是二叉搜索树
- [LeetCode] Minimum Absolute Difference in BST 二叉搜索树的最小绝对差
- [LeetCode] LFU Cache 最近最不常用页面置换缓存器
- [LeetCode] Convert a Number to Hexadecimal 数字转为十六进制
- [LeetCode] 212. Word Search II 词语搜索之二
- leetcode 538. Convert BST to Greater Tree 把二叉搜索树转换为累加树(简单)
- leetcode 240. Search a 2D Matrix II 搜索二维矩阵 II(中等)
- leetcode算法108.将有序数组转换为二叉搜索树