实现二叉搜索树（BST）的插入、查找和删除操作

题目描述
二叉搜索树（BST）是一种特殊的二叉树，满足以下性质：

• 左子树所有节点的值均小于根节点的值
• 右子树所有节点的值均大于根节点的值
• 左右子树也分别为二叉搜索树

题目要求实现BST的三个核心操作：插入新节点、查找指定值、删除指定节点，并保证操作后仍满足BST性质。

解题过程

1. BST的基础结构
首先定义树节点结构，包含值、左子节点和右子节点指针：

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

2. 查找操作

• 目标：判断值target是否在BST中
• 步骤：
  1. 从根节点开始比较
  2. 若target等于当前节点值，返回True
  3. 若target小于当前节点值，递归搜索左子树
  4. 若target大于当前节点值，递归搜索右子树
  5. 遇到空节点说明未找到，返回False

def search(root, target):
    if not root:
        return False
    if target == root.val:
        return True
    elif target < root.val:
        return search(root.left, target)
    else:
        return search(root.right, target)

• 时间复杂度：O(h)（h为树高，平衡时h=logN，最坏时h=N）

3. 插入操作

• 关键：新节点必须成为叶子节点，保持BST性质
• 步骤：
  1. 若树为空，直接创建新节点作为根节点
  2. 比较插入值与当前节点值：
     • 若小于当前值，递归插入左子树（若左子树空则直接挂载）
     • 若大于当前值，递归插入右子树（若右子树空则直接挂载）
     • 若相等，按约定处理（通常不允许重复值）

def insert(root, val):
    if not root:
        return TreeNode(val)  # 创建新节点
    if val < root.val:
        root.left = insert(root.left, val)  # 递归插入左子树
    elif val > root.val:
        root.right = insert(root.right, val)  # 递归插入右子树
    # 相等时不插入（或根据需求处理）
    return root  # 返回当前节点以维护结构

• 注意：通过root.left = insert(...)保证父子关系正确连接

4. 删除操作（最复杂）
分为三种情况处理：

• 情况1：目标节点为叶子节点
  直接删除（父节点对应指针置空）

• 情况2：目标节点有一个子节点
  用其子节点替代自身位置（类似链表删除）

• 情况3：目标节点有两个子节点

  1. 找到右子树中的最小节点（或左子树最大节点）
  2. 用该最小节点的值覆盖目标节点值
  3. 递归删除右子树中那个最小节点（此时转为情况1或2）

def delete(root, val):
    if not root:
        return None
    if val < root.val:
        root.left = delete(root.left, val)  # 在左子树中删除
    elif val > root.val:
        root.right = delete(root.right, val)  # 在右子树中删除
    else:  # 找到目标节点
        if not root.left:   # 情况1/2：无左子节点
            return root.right
        elif not root.right:  # 情况2：无右子节点
            return root.left
        else:  # 情况3：有两个子节点
            # 找到右子树最小节点
            min_node = root.right
            while min_node.left:
                min_node = min_node.left
            root.val = min_node.val  # 覆盖值
            root.right = delete(root.right, min_node.val)  # 删除重复节点
    return root

5. 关键细节说明

• 删除操作中的覆盖策略：
  情况3时，选择右子树最小节点（中序后继）替代当前节点，能保证BST性质：

  • 替代节点值大于左子树所有值（因来自右子树）
  • 替代节点值小于右子树剩余值（因是右子树最小值）

• 递归的返回值意义：
  每个递归调用返回当前子树的根节点，使得父节点能正确更新子指针

6. 综合示例
构建BST示例：依次插入[5,2,7,1,3]，删除节点2后的中序遍历结果应为[1,3,5,7]（保持有序性）

总结

• 插入/查找/删除的时间复杂度均与树高h相关
• 若树保持平衡（如AVL树、红黑树），h=logN，操作高效
• 删除操作是难点，需分情况处理，特别是双子树时的替代策略