不能简单用子树根替换，因BST要求左子树全小于右子树全大于；删除需分四类处理并更新父指针，双子时用后继值覆盖后递归删后继，且BST删除不维护平衡。

删除节点时，为什么不能简单用子树根直接替换？

因为 BST 的核心性质是「左子树所有值 left 或 right 子树根替代，会破坏该性质——比如用左子树最大值（即中序前驱）替换，才能保证左子树仍全小于它、右子树仍全大于它。

常见错误现象：Segmentation fault 或数据错乱，往往源于未正确更新父指针或未处理双子节点的后继查找逻辑。

• 单子节点或叶子节点：直接用非空子节点（或 nullptr）上移即可
• 双子节点：必须用中序前驱（左子树最右）或中序后继（右子树最左）替换，二者选其一并递归删除该前驱/后继节点
• 推荐统一用中序后继（右子树最小值），因右子树非空时一定存在，逻辑更稳定

C++ 中 delete_node 实现的关键分支与指针更新

核心难点不在查找，而在「替换后如何安全断开旧节点连接」。C++ 没有自动弱引用，父节点的 left/right 指针必须显式重定向。

典型错误：在递归调用 delete_node(root->right, key) 后，忘记将返回值赋给 root->right，导致修改丢失。

立即学习“C++免费学习笔记（深入）”；

C++ 算法竞赛自动化测试数据生成与校验框架

根据原题生成新题面、验证器及完整测试数据，自动套用 testlib 模板，用于用户要求生成测试数据时。

下载

• 递归函数必须返回 TreeNode*，调用方需更新对应子指针：root->left = delete_node(root->left, key);
• 找到目标节点后：
  • 无子节点 → delete root; return nullptr;
  • 仅左子 → auto tmp = root->left; delete root; return tmp;
  • 仅右子 → auto tmp = root->right; delete root; return tmp;
  • 双子 → 找右子树最小节点 successor，赋值 root->val = successor->val，再递归删 successor->val（此时它必为叶子或单子）

BST 删除本身不维护平衡，AVL / Red-Black 是另一层逻辑

很多初学者误以为「BST 删除要旋转」，其实标准 BST 定义不要求平衡；std::set 和 std::map 底层是红黑树，但那是封装好的容器，不是裸 BST 的责任。

如果你需要平衡，必须额外实现旋转和平衡因子更新——但那已不属于 BST 删除逻辑，而是 AVL 或 RBTree 的插入/删除配套机制。

• 纯 BST 删除后，树可能退化成链表，height 可能从 O(log n) 变成 O(n)
• 若你正在手写 AVL，删除后需自底向上回溯检查每个祖先的 balance factor，并在失衡点做 LL/RR/LR/RL 旋转
• 红黑树删除更复杂，需处理「双黑」情况，通常比插入多 3–4 倍代码量

一个易忽略的边界：后继节点可能带右子树

找中序后继（右子树最小值）时，很多人写成 while (cur->left) cur = cur->left;，这没错；但随后直接 delete successor; 就错了——因为 successor 可能有右子树（它只是右子树里最左的，不代表没右孩子）。

正确做法是：用 successor 的值覆盖待删节点后，**递归删除 successor 节点本身**，由同一套 delete_node 逻辑处理其子树衔接。

• 不要手动拼接 successor->right 到父节点——那会绕过递归基，漏掉深层调整
• 确保递归调用传入的是 successor->val（而非原 key），否则可能误删其他节点
• 若用前驱（左子树最大值），同理：它可能有左子树，必须递归删，不能直接摘除

实际编码时，最常出问题的不是算法思路，而是父子指针更新时机和递归返回值的承接。哪怕逻辑全对，漏写一行 root->right = delete_node(...)，整棵树就断开了。