在二叉搜索树 (BST) 中删除节点

Source: Dev.to

快速提醒：BST 有何特别之处？

• 左子树中的所有值都小于该节点。
• 右子树中的所有值都大于该节点。

这种顺序使得搜索、插入和删除都能高效进行。

问题描述

给定一棵 BST 的根节点和一个值 key。
删除具有该键的节点（如果存在），并返回更新后的树，确保树仍然是合法的 BST。

先找到目标节点

• 如果 key < root.val → 向左子树递归。
• 如果 key > root.val → 向右子树递归。
• 如果相等 → 该节点即为待删除节点。

三种删除情况

情况 1：节点没有子节点（叶子节点）

直接移除该节点：

return null;

情况 2：节点只有一个子节点

用唯一的子节点替代该节点。

• 只有右子节点 → return root.right;
• 只有左子节点 → return root.left;

情况 3：节点有两个子节点（最复杂的情况）

1. 寻找中序后继（右子树中最小的节点）。
2. 将后继的值复制到当前节点。
3. 从右子树中删除那个后继节点。

综合代码实现

class Solution {

    // Finds the inorder successor (smallest node in right subtree)
    public static TreeNode inOrderSuccessor(TreeNode root) {
        while (root.left != null) {
            root = root.left;
        }
        return root;
    }

    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null)
            return root;

        // Search for the node
        if (root.val > key) {
            root.left = deleteNode(root.left, key);
        } else if (root.val < key) {
            root.right = deleteNode(root.right, key);
        } else {
            // Found the node to delete

            // Case 1: No children
            if (root.left == null && root.right == null) {
                return null;
            }

            // Case 2: One child
            if (root.left == null) {
                return root.right;
            } else if (root.right == null) {
                return root.left;
            }

            // Case 3: Two children
            TreeNode successor = inOrderSuccessor(root.right);
            root.val = successor.val;
            root.right = deleteNode(root.right, successor.val);
        }

        return root;
    }
}

结语

• 理解 BST 的性质。
• 确定要删除的节点。
• 有条不紊地处理每一种删除情况。
• 保持树的结构完整。

多练习这种模式，绝大多数树相关的题目都会变得更易掌握。祝编码愉快！