如何在二叉搜索树中删除一个节点？

推荐答案

// www.javascriptcn.com code example
class TreeNode:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.val = key

def deleteNode(root, key):
    if not root:
        return root

    if key < root.val:
        root.left = deleteNode(root.left, key)
    elif key > root.val:
        root.right = deleteNode(root.right, key)
    else:
        if not root.left:
            return root.right
        elif not root.right:
            return root.left

        temp = findMin(root.right)
        root.val = temp.val
        root.right = deleteNode(root.right, temp.val)

    return root

def findMin(node):
    current = node
    while current.left:
        current = current.left
    return current

本题详细解读

1. 问题分析

在二叉搜索树（BST）中删除一个节点时，需要考虑以下几种情况：

• 节点是叶子节点（没有子节点）
• 节点只有一个子节点
• 节点有两个子节点

2. 解决方案

1. 查找要删除的节点：

   • 如果目标节点值小于当前节点值，递归地在左子树中查找。
   • 如果目标节点值大于当前节点值，递归地在右子树中查找。
   • 如果找到目标节点，进行删除操作。

2. 删除节点：

   • 情况1：节点是叶子节点：直接删除该节点。
   • 情况2：节点只有一个子节点：用其子节点替换该节点。
   • 情况3：节点有两个子节点：
     • 找到右子树中的最小节点（或左子树中的最大节点）。
     • 用该最小节点的值替换当前节点的值。
     • 删除右子树中的最小节点。

3. 代码实现

• deleteNode 函数递归地查找并删除目标节点。
• findMin 函数用于找到右子树中的最小节点。

4. 复杂度分析

• 时间复杂度：O(h)，其中 h 是树的高度。在最坏情况下（树为链表），时间复杂度为 O(n)。
• 空间复杂度：O(h)，递归调用栈的深度取决于树的高度。

通过这种方法，可以有效地在二叉搜索树中删除一个节点，同时保持树的二叉搜索性质。