450. 删除二叉搜索树中的节点
给定一个二叉搜索树的根节点 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
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/delete-node-in-a-bst
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
-
创建二叉树
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
-
1. 递归法
思路：
- 比较当前节点的值和要删除的节点的值，如果 key < root.val， 那么在左子树进行删除
- 如果 key > root.val, 那么在右子树进行删除
- 如果相等，则表示找到了要删除的节点，在判断该节点的左子树是否为空，如果是，返回右子树即可
- 如果右子树为空，则返回左子树即可
- 如果左右子树都不为空，我们需要找到比待删除节点大的最小节点，也就是右子树中的最小子树，使该节点作为删除后的节点
public TreeNode deleteNode(TreeNode root, int key) {
if (root == null) return null;
//要删除的值小于根节点值，那么在左子树中寻找
if (key < root.val) {
root.left = deleteNode(root.left, key);
return root;
} else if (key > root.val) { //右子树中查找
root.right = deleteNode(root.right, key);
return root;
} else { //找到该节点，进行删除
if (root.left == null) {
//左子树为空，删除节点，使用右节点替换
TreeNode rightNode = root.right;
root.right = null;
return rightNode;
} else if (root.right == null) {
//右子树为空，删除节点，使用左节点替换
TreeNode leftNode = root.left;
root.left = null;
return leftNode;
} else {
//左右子树均不为空，需要找到比待删除节点大的最小节点
// TreeNode successor = minimum(root.right);
// successor.left = root.left;
// successor.right = removeMin(root.right);
// root.left = root.right = null;
root.val = minimum(root.right).val;
root.right = removeMin(root.right);
return root;
}
}
}
/**
* 找到二叉搜索树中的最小节点
* @param node
* @return
*/
private TreeNode minimum(TreeNode node) {
if (node.left == null) return node;
return minimum(node.left);
}
/**
* 移除二叉搜索树中的最小节点，返回新的二叉搜索树的根
* @param node
* @return
*/
private TreeNode removeMin(TreeNode node) {
if (node.left == null) {
TreeNode rightNode = node.right;
node.right = null;
return rightNode;
// return node.right;
}
node.left = removeMin(node.left);
return node;
}
复杂度分析：
- 时间复杂度：O(log(n)), 也就是树的高度
- 空间复杂度：O(log(n)), 递归深度为树的高度
-
源码
-
我会每天更新新的算法，并尽可能尝试不同解法，如果发现问题请指正
- Github
