如何删除同时存在左右子树及后代的二叉搜索树(BST)根节点

对于同时存在左右子树的根节点，删除逻辑和BST中任意有两个子节点的节点删除逻辑一致，核心是找一个符合规则的节点替换根节点的值，再删除冗余的节点，全程不会破坏BST的左小右大性质。

可选实现方案（两种二选一即可） #

方案1：用中序后继（右子树最小节点）替换 #

• 遍历根节点的右子树，找到右子树中值最小的节点（即中序遍历序列里根节点的下一个节点）：从根的右孩子开始，一直向下找左子节点，直到某个节点没有左子节点，这个节点就是目标后继。
• 将后继节点的值赋值给根节点，此时根节点的值已经满足BST规则，只需要删除原来的后继节点即可。
• 后继节点最多只有右子节点（如果有左子节点它就不是右子树最小值），直接用它的右子节点替换它的位置即可：如果后继是根右孩子的左后代，就把后继父节点的左指针指向后继的右孩子；如果后继就是根的右孩子（说明根的右孩子没有左子树），就把根的右指针指向后继的右孩子。

方案2：用中序前驱（左子树最大节点）替换 #

逻辑和方案1对称：

• 遍历根节点的左子树，找到左子树中值最大的节点（即中序遍历序列里根节点的前一个节点）：从根的左孩子开始，一直向下找右子节点，直到某个节点没有右子节点，这个节点就是目标前驱。
• 将前驱节点的值赋值给根节点。
• 前驱节点最多只有左子节点，直接用它的左子节点替换它的位置即可。

代码示例（Python） #

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def delete_root_with_two_children(root: TreeNode) -> TreeNode:
    # 仅处理根节点同时存在左右子树的场景
    if not root or not root.left or not root.right:
        return root
    
    # 此处以方案1（找右子树最小节点）为例实现
    succ_parent = root
    succ = root.right
    # 找右子树最小节点
    while succ.left:
        succ_parent = succ
        succ = succ.left
    
    # 替换根节点值
    root.val = succ.val
    # 删除原后继节点
    if succ_parent == root:
        succ_parent.right = succ.right
    else:
        succ_parent.left = succ.right
    
    return root

实际使用时可以根据左右子树的高度选择方案，优先遍历更矮的子树找替换节点，既减少遍历耗时，也有利于维持树的平衡，避免树退化成链表。

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