LeetCode 题解之 450. Delete Node in a BST
程序员文章站
2022-04-24 23:45:45
...
450. Delete Node in a BST
题目描述和难度
- 题目描述:
给定一个二叉搜索树的根节点 root 和一个值 key,删除二叉搜索树中的 key 对应的节点,并保证二叉搜索树的性质不变。返回二叉搜索树(有可能被更新)的根节点的引用。
一般来说,删除节点可分为两个步骤:
- 首先找到需要删除的节点;
- 如果找到了,删除它。
说明: 要求算法时间复杂度为 O(h),h 为树的高度。
示例:
root = [5,3,6,2,4,null,7] key = 3 5 / \ 3 6 / \ \ 2 4 7 给定需要删除的节点值是 3,所以我们首先找到 3 这个节点,然后删除它。 一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。 5 / \ 4 6 / \ 2 7 另一个正确答案是 [5,2,6,null,4,null,7]。 5 / \ 2 6 \ \ 4 7
- 题目难度:中等。
- 英文网址:450. Delete Node in a BST 。
- 中文网址:450. 删除二叉搜索树中的节点 。
思路分析
求解关键:BST 的删除结点操作在《数据结构与算法》这一类的教科书上都有介绍。
- 虽然这个操作是计算机科学家 Hibbard 发明的,但其实这个操作非常简单且直观。
- 理解这个算法的关键在于保持 BST 中序遍历的顺序性,当待删除结点的左右结点都不为空的时候,让待删除结点的前驱结点或者后继结点代替它,这样就能成为一棵树,并且还是 BST,否则就变成森林,或者不保持 BST 中序遍历的顺序性了。
- 在草稿纸上很容易画出 BST 删除结点操作的这 3 种情况。
参考解答
参考解答1:用前驱结点代替
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
class Solution {
public TreeNode deleteNode(TreeNode root, int key) {
if (root == null) {
return null;
}
if (key < root.val) {
root.left = deleteNode(root.left, key);
return root;
}
if (key > root.val) {
root.right = deleteNode(root.right, key);
return root;
}
assert key == root.val;
if (root.left == null) {
TreeNode right = root.right;
root.right = null;
return right;
}
if (root.right == null) {
TreeNode left = root.left;
root.left = null;
return left;
}
TreeNode predecessor = maximum(root.left);
TreeNode predecessorCopy = new TreeNode(predecessor.val);
predecessorCopy.left = removeMax(root.left);
predecessorCopy.right = root.right;
root.left = null;
root.right = null;
return predecessorCopy;
}
private TreeNode removeMax(TreeNode node) {
if (node.right == null) {
TreeNode left = node.left;
node.left = null;
return left;
}
node.right = removeMax(node.right);
return node;
}
private TreeNode maximum(TreeNode node) {
if (node.right == null) {
return node;
}
return maximum(node.right);
}
}
参考解答2:用后继结点代替
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
/**
* https://leetcode-cn.com/problems/delete-node-in-a-bst/description/
*
* @author liwei
*/
public class Solution {
private TreeNode minNode(TreeNode node) {
while (node.left != null) {
node = node.left;
}
return node;
}
/**
* 删除一个二分搜索树中最小的节点,把新的二分搜索树的根返回回去
* 使用递归,要特别注意,定义的递归函数,返回的是,删除了最小值节点以后的新的二分搜索树的根
*
* @param node
* @return
*/
private TreeNode removeMin(TreeNode node) {
if (node.left == null) {
// 就是那个我们要删除的节点
TreeNode rightNode = node.right;
node.right = null;
return rightNode;
}
node.left = removeMin(node.left);
return node;
}
public TreeNode deleteNode(TreeNode root, int key) {
if (root == null) {
return null;
}
if (root.val < key) {
root.right = deleteNode(root.right, key);
return root;
} else if (root.val > key) {
root.left = deleteNode(root.left, key);
return root;
} else {
// 如果待删除的节点左孩子为空
if (root.left == null) {
TreeNode rightNode = root.right;
root.right = null;
return rightNode;
}
// 如果待删除的节点只有右孩子
if (root.right == null) {
TreeNode leftNode = root.left;
root.left = null;
return leftNode;
}
// 从它的右子树中拿到最小的
TreeNode successor = new TreeNode(minNode(root.right).val);
successor.left = root.left;
successor.right = removeMin(root.right);
root.left = null;
root.right = null;
return successor;
}
}
}
本篇文章的地址为 https://liweiwei1419.github.io/leetcode-solution/leetcode-0450-delete-node-in-a-bst ,如果我的题解有错误,或者您有更好的解法,欢迎您告诉我 [email protected] 。
.label-warning {
background-color: #f0ad4e;
}
.label-success {
background-color: #5cb85c;
}
.label-danger {
background-color: #d9534f;
}
.label {
display: inline;
padding: .2em .6em .3em;
font-size: 75%;
font-weight: 700;
line-height: 1;
color: #fff;
text-align: center;
white-space: nowrap;
vertical-align: baseline;
border-radius: .25em;
}