二叉搜索树的删除

情况三: 有两个子节点

前驱 后继

补充

补充：BST 删除节点按子树数量分三种情况：

• 情况一：叶子节点 —— 直接删除即可。
• 情况二：仅有一个子节点 —— 用唯一子节点顶替被删节点的位置。
• 情况三：有两个子节点（即原笔记中提到的）—— 在左子树中找前驱（左子树最大值）或在右子树中找后继（右子树最小值），用其值顶替被删节点，然后递归删除那个前驱/后继叶子，从而把问题归约为情况一/二。

function removeNode(root, key) {
  if (!root) return null;
  if (key < root.val) root.left = removeNode(root.left, key);
  else if (key > root.val) root.right = removeNode(root.right, key);
  else {
    if (!root.left) return root.right;
    if (!root.right) return root.left;
    // 两个子节点：用右子树的最小值（前驱可选）顶替
    let min = root.right;
    while (min.left) min = min.left;
    root.val = min.val;
    root.right = removeNode(root.right, min.val);
  }
  return root;
}

来源整理自：我的有道云笔记