能否通过该方法实现AVL/BST树的节点删除？

常规的节点删除流程是找到目标节点的中序前驱或后继，替换目标节点值后删除前驱/后继节点。现在提出一种替代方法，具体步骤如下：

• 找到待删除节点后，交换其与左子节点的数值
• 递归删除左子节点
• 若待删除节点无左子节点，则直接截断该节点，用其右子节点替换自身

本质逻辑是：将待删除节点持续与左子节点交换值，直到该节点无左子节点，此时截断该节点，将其父节点的左子节点替换为被截断节点的右子节点。这种方法无需查找中序前驱/后继，也不用修改待删除节点的数值。

以删除节点50为例：

结论 #

这种方法完全可行，核心逻辑和常规删除方法等价：

1. 每次交换待删除节点与左子节点的值，本质是把左子树的最右节点（即中序前驱）的值逐步“上浮”到待删除节点的位置
2. 递归删除左子节点的过程，最终就是删除原来的中序前驱节点——当节点无左子节点时，它就是左子树的最右节点，也就是原待删除节点的中序前驱
3. 无左子节点时直接用右子节点替换，这和常规删除逻辑完全一致

需要注意两点：

• 若在AVL树中使用该方法，每次递归删除后需重新平衡树结构，要求和常规删除流程一致
• 该方法会增加多次节点值交换操作，但最终得到的树结构与常规删除后的结构一致，BST/AVL的性质也能保持不变

内容的提问来源于stack exchange，提问作者user2277550