二叉搜索树 (BST) 删除节点 3 种情况详解：从递归到迭代，附 5 个 LeetCode 实战

二叉搜索树删除节点的3种情况与实战应用：从递归到迭代的深度解析

二叉搜索树（Binary Search Tree, BST）作为计算机科学中最基础且实用的数据结构之一，其删除操作一直是算法面试中的高频考点。本文将系统性地剖析BST删除节点的三种经典情况，对比递归与迭代两种实现范式，并通过5道LeetCode真题强化实战能力。

1. 二叉搜索树核心特性回顾

在深入删除操作之前，我们需要明确BST的三个基本性质：

1. 有序性：对于任意节点，左子树所有节点值 < 当前节点值 < 右子树所有节点值
2. 结构性：空树是BST，单个节点也是BST
3. 递归性：左右子树都是BST（递归定义）

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

BST的平均时间复杂度为O(log n)，但在最坏情况下（退化成链表）会恶化到O(n)。这就是为什么实际应用中更多使用平衡二叉搜索树（如AVL树、红黑树）。

关键认知：删除操作必须维护BST的有序性，这是所有实现方案的核心约束条件

2. 删除节点的三种情况分解

根据待删除节点的子节点数量，我们可以将问题划分为三类，每种情况需要不同的处理策略：

2.1 情况一：删除叶子节点（0个子节点）

这是最简单的情况，直接移除节点即可，不会影响树的结构性质。

操作步骤：

1. 定位到待删除节点
2. 将其父节点对应的指针置为null
3. 释放节点内存

可视化示例：

删除前： 41 / \ 20 65 / 50 删除50后： 41 / \ 20 65

2.2 情况二：删除只有一个子节点的节点

需要将被删除节点的子节点"提升"到其原有位置。

操作步骤：

1. 定位到待删除节点
2. 用其唯一子节点替换自身
3. 释放节点内存

可视化示例：

删除前： 41 / \ 20 65 / 50 删除65后： 41 / \ 20 50

2.3 情况三：删除有两个子节点的节点

最复杂的情况，需要找到合适的替代节点来保持BST性质。通常有两种策略：

1. 后继替换法：用右子树的最小节点（中序后继）替换
2. 前驱替换法：用左子树的最大节点（中序前驱）替换

标准操作流程（以后继替换为例）：

1. 找到待删除节点
2. 在其右子树中找到最小值节点（最左节点）
3. 用该最小值替换待删除节点的值
4. 递归删除右子树中的那个最小值节点

可视化示例：

删除前： 41 / \ 20 65 / \ 50 72 / \ 45 55 删除65后（用72替换）： 41 / \ 20 72 / \ 50 72 / \ 45 55

3. 递归实现方案详解

递归实现更直观地反映了BST的递归性质，代码通常更简洁。以下是Python实现：

def deleteNode(root: TreeNode, key: int) -> TreeNode: if not root: return None if key < root.val: root.left = deleteNode(root.left, key) elif key > root.val: root.right = deleteNode(root.right, key) else: # 情况1：叶子节点或单子节点 if not root.left: return root.right if not root.right: return root.left # 情况2：双子节点（找后继） successor = findMin(root.right) root.val = successor.val root.right = deleteNode(root.right, successor.val) return root def findMin(node): while node.left: node = node.left return node

时间复杂度分析：

• 最好/平均情况：O(log n)
• 最坏情况：O(n)（树退化为链表）

空间复杂度：

• 递归栈空间：O(h)，h为树高

4. 迭代实现方案剖析

迭代实现避免了递归调用栈的开销，更适合深度较大的树。以下是迭代版本的Python实现：

def deleteNodeIterative(root: TreeNode, key: int) -> TreeNode: curr = root parent = None # 第一阶段：搜索节点 while curr and curr.val != key: parent = curr curr = curr.left if key < curr.val else curr.right if not curr: # 未找到 return root # 第二阶段：删除节点 if not curr.left or not curr.right: child = curr.left if curr.left else curr.right if not parent: # 删除的是根节点 return child if parent.left == curr: parent.left = child else: parent.right = child else: # 两个子节点 successor_parent = curr successor = curr.right while successor.left: successor_parent = successor successor = successor.left curr.val = successor.val if successor_parent.left == successor: successor_parent.left = successor.right else: successor_parent.right = successor.right return root

关键区别点：

1. 需要显式维护parent指针
2. 删除操作分为搜索和修改两个独立阶段
3. 处理后继节点时需考虑其是否为右子树的直接根节点

5. 边界条件与易错点分析

在实际编码面试中，以下边界条件经常被忽视：

1. 删除根节点：需要特殊处理parent为None的情况
2. 重复值：标准BST通常不允许重复值，但某些变体允许
3. 内存管理：C++等语言需要手动释放节点内存
4. 空树处理：删除操作在空树上应安全返回
5. 节点不存在：应保持树结构不变

常见错误模式：

# 错误示例：未正确处理parent指针 def deleteNodeWrong(root, key): if not root: return None # ...找到节点后直接修改... node.val = successor.val # 只修改了值，未更新树结构 return root

6. LeetCode实战精讲

6.1 LeetCode 450. 删除二叉搜索树中的节点

这是最标准的BST删除问题，直接应用前述算法即可。注意题目要求返回修改后的根节点。

优化点：可以提前判断当找到节点时，如果它是叶子节点就直接返回None，减少递归深度。

6.2 LeetCode 701. 二叉搜索树中的插入操作

虽然题目是插入操作，但理解插入有助于反向理解删除。插入总是发生在叶子节点位置，而删除可能发生在任何位置。

6.3 LeetCode 669. 修剪二叉搜索树

这个问题可以看作是多节点删除的变种。解题关键在于：

if root.val < low: return trimBST(root.right, low, high) if root.val > high: return trimBST(root.left, low, high)

6.4 LeetCode 230. 二叉搜索树中第K小的元素

展示了BST中序遍历的有序性。删除操作中寻找后继节点的过程与此相关。

6.5 LeetCode 538. 把二叉搜索树转换为累加树

虽然是关于修改节点值的问题，但遍历顺序（右-根-左）与删除时寻找前驱节点的路径一致。

7. 性能对比与工程实践建议

实现方式	优点	缺点	适用场景
递归实现	代码简洁，逻辑直观	栈空间开销，深度大时可能溢出	树平衡较好的场景
迭代实现	无栈溢出风险，空间效率高	代码复杂，需维护parent指针	深度不可预测的大树

工程实践建议：

1. 在内存受限环境优先选择迭代实现
2. 递归实现更易于维护和调试
3. 考虑使用线索二叉树优化中序后继查找
4. 对于频繁删除的场景，建议使用平衡二叉搜索树

8. 高级变种与扩展思考

1. 带父指针的BST：简化了迭代实现中parent的维护
2. 懒惰删除：标记节点为已删除而非立即移除，适合频繁更新的场景
3. 线程二叉树：通过线索化加速中序前驱/后继查找
4. 支持重复值的BST：通常将count存储在节点中

// 支持重复值的节点结构 struct TreeNode { int val; int count; // 重复计数 TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), count(1), left(nullptr), right(nullptr) {} };

删除这类节点时，先减少count，只有当count为0时才实际移除节点。