【PTA】二叉搜索树的删除操作

二叉搜索树的删除操作涉及到以下几种情况：

1. 要删除的节点是叶子节点：直接删除即可。

2. 要删除的节点只有一颗子树：将子树接到要删除的节点的父节点上。

3. 要删除的节点有两颗子树：需要找到该节点的中序遍历的前驱或后继节点进行替换。

具体的删除操作如下：

1. 如果要删除的节点是根节点，直接将根节点置为空。

2. 如果要删除的节点是叶子节点，直接删除即可。

3. 如果要删除的节点只有一颗子树，将该子树接到要删除的节点的父节点上。

4. 如果要删除的节点有两颗子树，需要找到该节点的中序遍历的前驱或后继节点进行替换，这里以找后继节点为例：

a. 在该节点的右子树中找到最小的节点，即后继节点。

b. 将该节点的值赋值给要删除的节点。

c. 将后继节点删除。

下面是Java代码实现：

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 successor = findSuccessor(root.right);
            root.val = successor.val;
            root.right = deleteNode(root.right, successor.val);
        }
    }
    return root;
}

private TreeNode findSuccessor(TreeNode node) {
    while (node.left != null) {
        node = node.left;
    }
    return node;
}