删除二叉搜索树中的节点
难度:
标签:
题目描述
给定一个二叉搜索树的根节点 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
进阶： 要求算法时间复杂度为 O(h)，h 为树的高度。
代码结果
运行时间: 56 ms, 内存: 19.4 MB
// Java Stream solution for deleting a node in a BST
// Steps:
// 1. Find the node to delete using recursion.
// 2. Delete it and maintain BST properties using streams.
// 3. Use functional approach to handle the deletion and replacement.
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public class Solution {
public TreeNode deleteNode(TreeNode root, int key) {
if (root == null) return null;
if (key < root.val) {
// Stream approach to set left child
root.left = Optional.ofNullable(deleteNode(root.left, key)).orElse(null);
} else if (key > root.val) {
// Stream approach to set right child
root.right = Optional.ofNullable(deleteNode(root.right, key)).orElse(null);
} else {
if (root.left == null) return root.right;
if (root.right == null) return root.left;
TreeNode minNode = getMin(root.right);
root.val = minNode.val;
root.right = Optional.ofNullable(deleteNode(root.right, minNode.val)).orElse(null);
}
return root;
}
private TreeNode getMin(TreeNode node) {
while (node.left != null) node = node.left;
return node;
}
}
解释
方法:
这个题解使用递归的方法来删除二叉搜索树中的节点。首先判断当前节点是否为空，如果为空则直接返回。然后比较当前节点的值与要删除的值，如果当前节点的值小于要删除的值，则递归删除右子树中的节点；如果当前节点的值大于要删除的值，则递归删除左子树中的节点。如果当前节点的值等于要删除的值，则需要分情况处理：1. 如果当前节点没有左子树，则直接返回右子树；2. 如果当前节点没有右子树，则直接返回左子树；3. 如果当前节点既有左子树又有右子树，则找到右子树中的最小节点（即后继节点），将其左子树设为当前节点的左子树，然后返回当前节点的右子树。最后返回当前节点。
时间复杂度:
O(log(n))
空间复杂度:
O(log(n))
代码细节讲解
🦆
在递归删除节点时，如何确保修改的是正确的子树指针，特别是在动态改变树结构的情况下？
▷🦆
当找到要删除的节点且该节点同时拥有左右子树时，选择右子树中的最小节点作为后继节点的原因是什么？
▷🦆
在找到右子树的最小节点后，原题解中没有提及如何处理这个最小节点原先所在的位置。这个遗漏会如何影响算法的执行及结果？
▷