TikTok BST 查找与删除：根变化和后继替换

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 严格BST、无环、键唯一；search返回节点或None，delete返回新根，不承诺删除保留所有节点身份。

解题路线

1. search每步按目标与当前值比较只进入一侧，缩小候选子树；找不到返回None。
2. 删除先定位node及parent。零/一孩子时parent链接替换成唯一孩子或None；dummy让删除根也走统一链接修改。
3. 两孩子用右子树最小后继值替换当前，再删除那个后继；后继无左孩子，可直接用其右孩子接回。要覆盖后继就是直接右孩子的情况。
4. 若调用方持有节点身份，复制value改变的是哪个对象需要约定；要求真正移除指定节点则采用节点移植而非值复制。

手动走一遍

根5、左3、右8、8左6，删5用6替换，再从右子树删除6；中序仍递增。删除唯一根返回None；删除不存在键保持结构。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

class Node:
    def __init__(self, value, left=None, right=None):
        self.value, self.left, self.right = value, left, right


def search(root, value):
    while root is not None:
        if root.value == value:
            return root
        root = root.left if value < root.value else root.right
    return None


def delete(root, value):
    """Strict BST; mutate pointers/values, return possibly new root.
    A two-child deletion copies successor value; node identity is not promised."""
    dummy = Node(None, left=root)
    parent, node = dummy, root
    while node is not None and node.value != value:
        parent, node = node, node.left if value < node.value else node.right
    if node is None:
        return root
    if node.left is not None and node.right is not None:
        successor_parent, successor = node, node.right
        while successor.left is not None:
            successor_parent, successor = successor, successor.left
        node.value = successor.value
        parent, node = successor_parent, successor
    child = node.left if node.left is not None else node.right
    if parent.left is node:
        parent.left = child
    else:
        parent.right = child
    return dummy.left

复杂度

查找/删除 O(h)时间，迭代 O(1)工作空间；未平衡树 h可n，不承诺O(log n)。

易错点与追问

容易失分的边界

• 删除根却不返回新根。
• 两孩子直接接一侧丢另一侧。
• 后继右孩子被漏。

继续深挖

• 重复值合同怎样改变操作？
• 如何通过旋转维护平衡？