LeetCode题练习与总结：删除二叉搜索树中的节点--450

一、题目描述

给定一个二叉搜索树的根节点 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, 10^4].
-10^5 <= Node.val <= 10^5
节点值唯一
root 是合法的二叉搜索树
-10^5 <= key <= 10^5

二、解题思路

查找节点：由于是二叉搜索树，我们可以利用其性质来快速定位要删除的节点。二叉搜索树的性质是：对于任意节点，其左子树的所有节点值都小于该节点值，其右子树的所有节点值都大于该节点值。因此，我们可以从根节点开始，比较当前节点值与key的大小，决定向左还是向右搜索。
删除节点：找到要删除的节点后，根据节点的情况进行删除：
- 节点是叶子节点：直接删除，即返回null。
- 节点只有一个子节点：用子节点替代当前节点，返回子节点。
- 节点有两个子节点：找到右子树中的最小节点（或左子树中的最大节点），用它来替代要删除的节点，然后删除该最小（或最大）节点。

三、具体代码

class Solution {public TreeNode deleteNode(TreeNode root, int key) {if (root == null) {return null;}// 查找要删除的节点if (key < root.val) {root.left = deleteNode(root.left, key);} else if (key > root.val) {root.right = deleteNode(root.right, key);} else {// 找到要删除的节点，进行删除操作if (root.left == null) {return root.right; // 只有一个右子节点或没有子节点} else if (root.right == null) {return root.left; // 只有一个左子节点} else {// 找到右子树中的最小节点TreeNode minNode = findMin(root.right);// 用最小节点替代当前节点root.val = minNode.val;// 删除右子树中的最小节点root.right = deleteNode(root.right, minNode.val);}}return root;}// 辅助函数，找到以node为根的树中的最小节点private TreeNode findMin(TreeNode node) {while (node.left != null) {node = node.left;}return node;}
}

这段代码首先递归地查找要删除的节点，然后根据节点的情况进行相应的删除操作。如果节点有两个子节点，我们通过findMin函数找到右子树中的最小节点，用它来替代要删除的节点，然后递归地删除右子树中的最小节点。

四、时间复杂度和空间复杂度

1. 时间复杂度

查找节点：在二叉搜索树中查找一个节点的时间复杂度是 O(h)，其中 h 是树的高度。在平衡的二叉搜索树中，h = log(n)，其中 n 是树中节点的数量。在最坏的情况下（树完全倾斜），h = n。
删除节点：
- 节点是叶子节点：直接删除，时间复杂度为 O(1)。
- 节点只有一个子节点：直接用子节点替代，时间复杂度为 O(1)。
- 节点有两个子节点：需要找到右子树中的最小节点，这需要 O(h) 的时间，然后删除该最小节点，这同样需要 O(h) 的时间。

综上所述，删除操作的时间复杂度是 O(h)。

因此，整体的时间复杂度是 O(h)，在平衡树中是 O(log(n))，在最坏情况下是 O(n)。

2. 空间复杂度

递归栈空间：由于使用递归，在最坏情况下，如果树完全倾斜，递归的深度将达到 n，因此递归栈的空间复杂度是 O(n)。
辅助空间：在删除节点时，除了递归栈外，我们只使用了常数个额外空间（例如用于存储最小节点的变量），因此辅助空间复杂度是 O(1)。

综合以上两点，整体的空间复杂度是 O(n)，其中 n 是树中节点的数量。在平衡树中，空间复杂度可以降低到 O(log(n))。

五、总结知识点

二叉搜索树（BST）的性质：
- 对于任意节点，其左子树的所有节点值都小于该节点值。
- 对于任意节点，其右子树的所有节点值都大于该节点值。
递归：
- 递归是一种常用的算法设计方法，用于在树形结构中进行遍历或修改。
- 在此代码中，递归用于在二叉搜索树中查找和删除指定的节点。
递归的基本情况与递归步骤：
- 基本情况（Base Case）：递归的终止条件，如 if (root == null)。
- 递归步骤（Recursive Step）：递归调用的部分，如 root.left = deleteNode(root.left, key)。
指针操作：
- 代码中使用了指针（在Java中称为引用）来修改二叉树的结构，如在删除节点时将父节点的引用指向子节点。
节点删除的三种情况：
- 叶子节点：直接删除，返回null。
- 只有一个子节点的节点：用子节点替代当前节点。
- 有两个子节点的节点：找到右子树中的最小节点（或左子树中的最大节点）来替代当前节点，然后删除该最小（或最大）节点。
辅助函数：
- findMin 函数用于找到以某个节点为根的树中的最小节点，这是通过不断向左遍历直到找到最左边的节点实现的。