力扣-删除二叉搜索树中的节点
- January 16, 2021
一、题目描述：
给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。
一般来说，删除节点可分为两个步骤：
首先找到需要删除的节点； 如果找到了，删除它。 说明： 要求算法时间复杂度为 O(h)，h 为树的高度。
示例:
root = [5,3,6,2,4,null,7] key = 3
给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。
一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。
另一个正确答案是 [5,2,6,null,4,null,7]。
二、解答
分析
解题思路： 首先，这个题目可以根据删除的节点的左右节点来判断。
而找到该节点是非常简单的，因为这棵树是二叉搜索树，而二叉搜索树的特性，左节点的值一定小于该节点值，右节点的值一定大于该节点的值，所以直接搜索就可以找到该值。
所以重点在于怎么判断该节点的左右节点的情况。
大致可以分为四种：
- 该节点没有左节点，也没有右节点
- 该节点没有左节点，但有右节点
- 该节点有左节点，但没有右节点
- 该节点有左节点，也有右节点
第一种：对于第一种情况，直接将该节点删除即可。 第二种：对于第二种情况，直接删除节点，将左节点代替该节点。 第三种：对于第三种情况：直接删除节点，将右节点代替该节点。 第四种：对于第四种情况，又可以分为三种情况：
- 该节点的左节点没有右节点，将左节点代替该节点。
- 该节点的右节点没有左节点，将右节点代替该节点。
- 对于都有的情况，为了保证二叉搜索树的结构，我们 ① ：可以用该节点的左节点最右节点的值代替该节点；②：也可以用该节点的右节点的最左节点的值代替该节点。
而对于最后的情况，也就是第四种情况的第三种情况， 需要注意 ①中，如果最右节点还有左节点，我们可以用最右节点的左节点的值代替最右节点所在的位置； ②中，如果最左节点还有右节点，我们可以用最左节点的右节点的值代替最左节点所在的位置。
再一次总结归纳： 其实，最后第四种情况的第三种就包括了前面所有的方面，
在找到该节点后：
- 如果该节点的左节点不为空，我们用该节点的左节点最右节点的值代替该节点；
- 否则，如果该节点的右节点不为空，我们可以用该节点的右节点的最左节点的值代替该节点。
- 否则，将该节点置空。
找到该节点，非常容易，因为左节点的值一定小于该节点值，右节点的值一定大于该节点的值。
所以，从根节点开始遍历
- 如果遍历到的节点的值大于该值，该值一定处于该节点的右子树，往右遍历即可。
- 否则，如果遍历到的节点的值小于该值，该值一定处于该节点的左子树，往左遍历即可。
- 否则，就是找到了该值，在进行上述操作即可。
时间复杂度：O(h)，其中 n 为树的高度。
代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public TreeNode deleteNode(TreeNode root, int key) {
if(root!=null){
if(root.val == key){
if(root.left != null){
root.val = leftMax(root);
root.left = deleteNode(root.left, root.val);
} else if(root.right != null){
root.val = rightMin(root);
root.right = deleteNode(root.right, root.val);
} else {
root = null;
}
}else if(root.val>key){
root.left = deleteNode(root.left,key);
}else{
root.right = deleteNode(root.right,key);
}
return root;
}
return null;
}
public int rightMin(TreeNode root) {
root = root.right;
while (root.left != null) root = root.left;
return root.val;
}
public int leftMax(TreeNode root) {
root = root.left;
while (root.right != null) root = root.right;
return root.val;
}
}
执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户 内存消耗：39.2 MB, 在所有 Java 提交中击败了8.92%的用户
三、官方解答
class Solution {
/*
One step right and then always left
*/
public int successor(TreeNode root) {
root = root.right;
while (root.left != null) root = root.left;
return root.val;
}
/*
One step left and then always right
*/
public int predecessor(TreeNode root) {
root = root.left;
while (root.right != null) root = root.right;
return root.val;
}
public TreeNode deleteNode(TreeNode root, int key) {
if (root == null) return null;
// delete from the right subtree
if (key > root.val) root.right = deleteNode(root.right, key);
// delete from the left subtree
else if (key < root.val) root.left = deleteNode(root.left, key);
// delete the current node
else {
// the node is a leaf
if (root.left == null && root.right == null) root = null;
// the node is not a leaf and has a right child
else if (root.right != null) {
root.val = successor(root);
root.right = deleteNode(root.right, root.val);
}
// the node is not a leaf, has no right child, and has a left child
else {
root.val = predecessor(root);
root.left = deleteNode(root.left, root.val);
}
}
return root;
}
}
本文首发于CSDN，作者：lomtom 原文链接：https://blog.csdn.net/qq_41929184/article/details/112662236 🔗 个人网站：https://lomtom.top 🔗，公众号：博思奥园，同步更新。
你的支持就是我最大的动力。
