BST 删除：三种情况
使用中序后继处理删除叶节点、删除单子节点和删除双子节点三种情况，从零实现该算法。
BST 删除：三种情况 是 CoddyKit 上的免费 Coding Interview Prep 课时。 这是第 2 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Coding Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Coding Interview Prep 课程共包含 4 节课。
为什么 BST 删除很棘手
BST 删除是三种核心操作中最复杂的一个，因为移除节点时必须保持整棵树的 BST 性质。根据节点的子节点情况，共有三种不同情况：没有子节点（叶节点）、有一个子节点或有两个子节点。每种情况都需要不同的策略。面试官喜欢考察这个问题，因为它能测试指针操作、边界情况思维以及对中序后继概念的掌握。
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# Three cases for deleting a node:
# Case 1: Leaf node (no children) -> simply remove it
# Case 2: One child -> replace node with its child
# Case 3: Two children -> replace value with in-order successor
# then delete the in-order successor
print('BST delete: 3 cases based on number of children')情况 1：删除叶节点
叶节点没有子节点。删除操作很简单：从递归调用中返回 None，这样父节点就会将其指针（左指针或右指针）设置为空值。这是所有 BST 删除实现都必须首先处理的基本情况。请确认只有一个节点的特殊情况也能正常工作（此时根节点就是叶节点）。
def find_min(node):
while node.left:
node = node.left
return node
# Demonstrating leaf deletion:
root = TreeNode(5)
root.left = TreeNode(3)
root.right = TreeNode(7)
root.left.left = TreeNode(1) # leaf
root.left.right = TreeNode(4) # leaf
# To delete node 1 (leaf): set root.left.left = None
root.left.left = None
print(root.left.left) # None -- deleted
print(root.left.val) # 3 still intact案例 2：只有一个子节点的节点
当一个节点恰好有一个子节点时，请用该子节点替换此节点。在递归调用中返回这个非空子节点，以便更新父节点的指针，跳过被删除的节点。无论这个子节点位于左侧还是右侧，这种做法都能顺利工作——只需返回实际存在的那个子节点。
# Demonstrating one-child deletion:
# Tree: 5
# / \
# 3 7
# \
# 4
# Delete node 3 (has only right child 4):
# Result: 5
# / \
# 4 7
root = TreeNode(5)
root.left = TreeNode(3)
root.right = TreeNode(7)
root.left.right = TreeNode(4)
# In the recursive implementation:
# When we reach node 3 and it has no left child,
# we return root.right (node 4) to the parent.
# Parent sets its left pointer to 4, skipping 3.
print('One-child case: return the surviving child')案例 3：有两个子节点的节点
当一个节点有两个子节点时，不能直接将其删除。相反，请找到该节点的中序后继（右子树中的最小值），将其值复制到当前节点中，然后从右子树中删除这个中序后继。后继节点至多有一个子节点（没有左子节点），因此删除它时会落入案例 1 或案例 2——这些情况我们已经知道如何处理。
# Demonstrating two-child deletion:
# Tree: 5
# / \
# 3 7
# / \
# 6 9
# Delete node 5 (two children 3 and 7):
# In-order successor = 6 (smallest in right subtree)
# Step 1: replace 5's value with 6
# Step 2: delete 6 from right subtree
# Result: 6
# / \
# 3 7
# \
# 9
print('Two-child case: replace with in-order successor')完整的 BST 删除实现
完整的递归删除操作会组合这三种情况。通过比较值找到要删除的节点，然后处理相应的情况。在每一层返回（可能已经修改过的）根节点，并将其重新赋值给 root.left 或 root.right，这种模式无需显式跟踪父节点，就能优雅地处理所有指针更新。时间复杂度为 O(h)。
def delete_node(root, key):
if not root:
return None # key not found
if key < root.val:
root.left = delete_node(root.left, key)
elif key > root.val:
root.right = delete_node(root.right, key)
else: # found the node to delete
if not root.left: # Case 1 or 2: no left child
return root.right
if not root.right: # Case 2: no right child
return root.left
# Case 3: two children -> find in-order successor
successor = find_min(root.right)
root.val = successor.val # copy successor value up
root.right = delete_node(root.right, successor.val) # delete successor
return root
root = TreeNode(5)
root.left = TreeNode(3)
root.right = TreeNode(7)
root.right.left = TreeNode(6)
root.right.right = TreeNode(9)
root = delete_node(root, 5)
print(root.val) # 6 (successor replaced 5)为什么使用中序后继
使用中序后继（右子树的最小值）而不是左子树的最大值，是因为两者都是有效选择——使用任意一个都能保持 BST 性质。中序前驱（左子树的最大值）同样可行。有些实现会交替使用二者，以使树保持平衡。在面试中，更常见的要求是实现中序后继版本；请说明使用前驱同样有效。
# Both approaches are valid for two-child deletion:
# Option A: Replace with in-order SUCCESSOR (min of right subtree)
# - Successor goes to current position
# - Delete successor from right subtree
# Option B: Replace with in-order PREDECESSOR (max of left subtree)
# - Predecessor goes to current position
# - Delete predecessor from left subtree
def find_max(node):
while node.right:
node = node.right
return node
# Using predecessor:
def delete_node_pred(root, key):
if not root:
return None
if key < root.val:
root.left = delete_node_pred(root.left, key)
elif key > root.val:
root.right = delete_node_pred(root.right, key)
else:
if not root.left:
return root.right
if not root.right:
return root.left
pred = find_max(root.left)
root.val = pred.val
root.left = delete_node_pred(root.left, pred.val)
return root
print('Both successor and predecessor deletion are correct')删除具有某个值的所有节点
有一种变体要求您删除值处于某个范围内或满足某个条件的所有节点。对于 BST，这种操作很高效：根据比较结果递归进入相应的子树，并在条件匹配的每个位置执行删除操作。BST 删除的递归结构可以自然扩展到这些场景，无需额外进行一次单独的遍历。
# Delete all nodes with values outside [low, high]
def trim_bst(root, low, high):
if not root:
return None
if root.val < low:
# Entire left subtree is also < low, skip to right
return trim_bst(root.right, low, high)
if root.val > high:
# Entire right subtree is also > high, skip to left
return trim_bst(root.left, low, high)
# Current node is within range
root.left = trim_bst(root.left, low, high)
root.right = trim_bst(root.right, low, high)
return root
root = TreeNode(3)
root.left = TreeNode(0)
root.right = TreeNode(4)
root.left.right = TreeNode(2)
root.left.right.left = TreeNode(1)
root = trim_bst(root, 1, 3)
print(root.val, root.left.val) # 3 2BST 迭代器模式
BST 迭代器（LeetCode #173）会按排序顺序一次返回一个元素，平均时间复杂度为 O(1)，空间复杂度为 O(h)。请使用一个栈来模拟迭代式中序遍历：构造时，从根节点开始将所有左侧节点压入栈中。调用 next() 时，弹出栈顶节点，然后将右子树中的所有左侧节点压入栈中。这是对迭代式中序算法的受控展开。
class BSTIterator:
def __init__(self, root):
self.stack = []
self._push_left(root)
def _push_left(self, node):
while node:
self.stack.append(node)
node = node.left
def next(self):
node = self.stack.pop()
if node.right:
self._push_left(node.right)
return node.val
def has_next(self):
return bool(self.stack)
root = TreeNode(7)
root.left = TreeNode(3)
root.right = TreeNode(15)
root.right.left = TreeNode(9)
it = BSTIterator(root)
while it.has_next():
print(it.next(), end=' ') # 3 7 9 15删除节点：复杂度分析
BST 删除的时间复杂度为 O(h)，其中 h 是树的高度。对于平衡 BST，复杂度为 O(log n)；对于倾斜树，复杂度会退化为 O(n)。查找中序后继最多会在右子树中额外进行一次 O(h) 遍历，但不会改变总体复杂度。在递归实现中，空间复杂度为调用栈所需的 O(h)。
# Complexity summary for BST operations:
# Operation | Balanced | Skewed
# ----------|-----------|-------
# Search | O(log n) | O(n)
# Insert | O(log n) | O(n)
# Delete | O(log n) | O(n)
# Min/Max | O(log n) | O(n)
# In-order | O(n) | O(n) (visits all nodes)
# The key: BST guarantees these complexities only when balanced.
# Python standard library has no balanced BST.
# Use sortedcontainers.SortedList for O(log n) ops in practice.
print('All BST core ops are O(h): O(log n) balanced, O(n) skewed')BST 中的两数之和
BST 中的两数之和 IV要求判断是否存在两个节点，使它们的和等于目标值。一种方法是使用集合：在中序遍历的同时收集值，并检查 target - current 是否已经存在于集合中。更优雅的方法是同时使用一个正向 BST 迭代器和一个反向 BST 迭代器（类似双指针）——除了每个迭代器的栈所需的 O(h) 空间之外，不需要额外空间。
def find_target_bst(root, k):
seen = set()
def inorder(node):
if not node:
return False
if inorder(node.left):
return True
if k - node.val in seen:
return True
seen.add(node.val)
return inorder(node.right)
return inorder(root)
root = TreeNode(5)
root.left = TreeNode(3)
root.right = TreeNode(6)
root.left.left = TreeNode(2)
root.left.right = TreeNode(4)
root.right.right = TreeNode(7)
print(find_target_bst(root, 9)) # True (2+7)
print(find_target_bst(root, 28)) # False将 BST 转换为累加树
累加树（LeetCode #538）会将 BST 中每个节点的值替换为所有大于或等于它的值之和。关键思路是执行反向中序遍历（右子树 → 根节点 → 左子树），按递减顺序访问节点并累加运行中的总和。时间复杂度为 O(n)，空间复杂度为 O(h)。
def bst_to_gst(root):
acc = [0] # running accumulated sum
def reverse_inorder(node):
if not node:
return
reverse_inorder(node.right) # visit larger values first
acc[0] += node.val
node.val = acc[0] # replace with cumulative sum
reverse_inorder(node.left)
reverse_inorder(root)
return root
root = TreeNode(4)
root.left = TreeNode(1)
root.right = TreeNode(6)
root.right.left = TreeNode(5)
root.right.right = TreeNode(7)
bst_to_gst(root)
print(root.val) # 4+5+6+7 = 22
print(root.right.val) # 5+6+7 = 18快速检查
请测试您对本课中数据结构与算法——编程面试准备相关概念的理解。
课程回顾
在本课中，您学习了：BST 删除的三种情况（叶节点、一个子节点、两个子节点）、用于删除有两个子节点节点的中序后继技巧，以及 BST 迭代器和 BST 转累加树等简洁的递归模式。接下来，我们将验证 BST 的正确性，并利用中序遍历的性质。
常见问题解答
「BST 删除：三种情况」课时是免费的吗？
是的 — 「BST 删除：三种情况」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Coding Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 Coding Interview Prep 课程共包含 4 节课。
「BST 删除：三种情况」这节课中我会学到什么？
使用中序后继处理删除叶节点、删除单子节点和删除双子节点三种情况，从零实现该算法。 你通过在浏览器中直接运行的动手代码来练习 Coding Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 Coding Interview Prep 需要有经验吗？
无需任何先前经验。CoddyKit 上的 Coding Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 2 节课，共 4 节。
「BST 删除：三种情况」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 Coding Interview Prep 课中编写并运行代码吗？
能。每节 Coding Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。
此课程中的所有课时
- BST 插入与查找
- BST 删除：三种情况
- 验证 BST 与中序性质
- 第 K 小、区间和与 BST 转有序数组