删除二叉搜索树中的节点

难度: Medium

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

进阶： 要求算法时间复杂度为 O(h)，h 为树的高度。

Submission

运行时间: 56 ms

内存: 19.4 MB

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
        if root is None:
            return
        if root.val < key:
            root.right = self.deleteNode(root.right, key)
        elif root.val > key:
            root.left = self.deleteNode(root.left, key)
        else:
            if root.left is None:
                return root.right
            if root.right is None:
                return root.left
            successor = root.right
            while successor.left:
                successor = successor.left
            successor.left = root.left
            return root.right
        return root

Explain

这个题解使用递归的方法来删除二叉搜索树中的节点。首先判断当前节点是否为空，如果为空则直接返回。然后比较当前节点的值与要删除的值，如果当前节点的值小于要删除的值，则递归删除右子树中的节点；如果当前节点的值大于要删除的值，则递归删除左子树中的节点。如果当前节点的值等于要删除的值，则需要分情况处理：1. 如果当前节点没有左子树，则直接返回右子树；2. 如果当前节点没有右子树，则直接返回左子树；3. 如果当前节点既有左子树又有右子树，则找到右子树中的最小节点（即后继节点），将其左子树设为当前节点的左子树，然后返回当前节点的右子树。最后返回当前节点。

时间复杂度: O(log(n))

空间复杂度: O(log(n))

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
        # 如果当前节点为空，直接返回
        if root is None:
            return
        
        # 如果当前节点的值小于要删除的值，递归删除右子树中的节点
        if root.val < key:
            root.right = self.deleteNode(root.right, key)
        # 如果当前节点的值大于要删除的值，递归删除左子树中的节点
        elif root.val > key:
            root.left = self.deleteNode(root.left, key)
        # 如果当前节点的值等于要删除的值，需要分情况处理
        else:
            # 如果当前节点没有左子树，直接返回右子树
            if root.left is None:
                return root.right
            # 如果当前节点没有右子树，直接返回左子树
            if root.right is None:
                return root.left
            
            # 如果当前节点既有左子树又有右子树，找到右子树中的最小节点（即后继节点）
            successor = root.right
            while successor.left:
                successor = successor.left
            # 将后继节点的左子树设为当前节点的左子树
            successor.left = root.left
            # 返回当前节点的右子树
            return root.right
        
        # 返回当前节点
        return root

Explore

在递归过程中，通过比较当前节点的值与要删除的键值来确定是应该递归进入左子树还是右子树。这一递归逻辑确保了每一步的操作都是针对正确的子树进行的。在修改子树时，通过返回值来更新父节点指向的子树指针，即通过`root.left = self.deleteNode(root.left, key)`或`root.right = self.deleteNode(root.right, key)`来确保子树的更新反映到整个树结构中。

在二叉搜索树中，右子树中的最小节点（或左子树中的最大节点）是替代被删除节点的最佳选择，因为它保持了二叉搜索树的性质。选择右子树中的最小节点作为后继节点是因为这个节点将是比当前节点值大的最小节点，确保所有左侧的节点值仍然小于替代节点，而所有右侧的节点值仍然大于替代节点。

在使用后继节点替换被删除节点后，需要适当处理后继节点原先的位置，通常这意味着移除后继节点但保留其子树。题解中未明确说明如何处理后继节点原位置的遗漏可能导致树结构的不一致或者数据丢失。正确做法应包括将后继节点从其原位置删除，这通常涉及将后继节点的右子树（后继节点不应有左子树，因为它是最小节点）接到其父节点的左链接上。未正确处理这一点，可能会导致重复节点或树结构错误。