Delete Node in a BST,LeetCode,450

好的，我们来详细讨论一下 LeetCode 上的第 450 题：删除二叉搜索树（BST）中的节点。

题目描述

给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回删除后的二叉搜索树的根节点。

解题思路

删除二叉搜索树中的节点可以分为以下几种情况：

1. 节点不存在：如果 root 为空或者找不到 key，直接返回 root。
2. 节点是叶子节点：直接删除该节点，返回 null。
3. 节点只有一个子节点：删除该节点，并用其子节点替代。
4. 节点有两个子节点：
   • 找到该节点的右子树中的最小节点（即后继节点）。
   • 将该节点的值替换为后继节点的值。
   • 删除后继节点。

代码实现

以下是使用递归实现的代码：

class TreeNode: def init(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right

    if key < root.val:
        root.left = self.deleteNode(root.left, key)
    elif key > root.val:
        root.right = self.deleteNode(root.right, key)
    else:
        # 找到了要删除的节点
        if not root.left:
            return root.right
        elif not root.right:
            return root.left
        else:
            # 找到右子树中的最小节点
            min_node = self.findMin(root.right)
            root.val = min_node.val
            root.right = self.deleteNode(root.right, min_node.val)

    return root

def findMin(self, node: TreeNode) -> TreeNode:
    while node.left:
        node = node.left
    return node

详细解释

1. 基本情况：
   • 如果 root 为空，直接返回 null。
2. 递归查找：
   • 如果 key 小于当前节点的值，递归地在左子树中查找并删除。
   • 如果 key 大于当前节点的值，递归地在右子树中查找并删除。
3. 删除操作：
   • 当找到要删除的节点时，根据其子节点的数量进行不同的处理：
     • 如果没有左子节点，返回右子节点。
     • 如果没有右子节点，返回左子节点。
     • 如果有两个子节点，找到右子树中的最小节点（后继节点），将其值赋给当前节点，并递归地删除后继节点。
4. 辅助函数 findMin：
   • 用于找到某个节点的右子树中的最小节点。

复杂度分析

• 时间复杂度：O(h)，其中 h 是树的高度。在最坏情况下，树可能是一条链，时间复杂度为 O(n)。
• 空间复杂度：O(h)，递归调用栈的深度。

总结

删除二叉搜索树中的节点是一个经典问题，需要处理多种情况。通过递归的方式，我们可以简洁地实现这一功能。关键在于正确处理有两个子节点的节点，通过找到后继节点并进行替换，保证二叉搜索树的性质不变。

希望这个详细的解答对你有所帮助！如果有任何进一步的问题，欢迎继续提问。