 删除节点 3 种情况详解：从递归到迭代，附 5 个 LeetCode 实战)
二叉搜索树删除节点的3种情况与实战应用从递归到迭代的深度解析二叉搜索树Binary Search Tree, BST作为计算机科学中最基础且实用的数据结构之一其删除操作一直是算法面试中的高频考点。本文将系统性地剖析BST删除节点的三种经典情况对比递归与迭代两种实现范式并通过5道LeetCode真题强化实战能力。1. 二叉搜索树核心特性回顾在深入删除操作之前我们需要明确BST的三个基本性质有序性对于任意节点左子树所有节点值 当前节点值 右子树所有节点值结构性空树是BST单个节点也是BST递归性左右子树都是BST递归定义class TreeNode: def __init__(self, val0, leftNone, rightNone): self.val val self.left left self.right rightBST的平均时间复杂度为O(log n)但在最坏情况下退化成链表会恶化到O(n)。这就是为什么实际应用中更多使用平衡二叉搜索树如AVL树、红黑树。关键认知删除操作必须维护BST的有序性这是所有实现方案的核心约束条件2. 删除节点的三种情况分解根据待删除节点的子节点数量我们可以将问题划分为三类每种情况需要不同的处理策略2.1 情况一删除叶子节点0个子节点这是最简单的情况直接移除节点即可不会影响树的结构性质。操作步骤定位到待删除节点将其父节点对应的指针置为null释放节点内存可视化示例删除前 41 / \ 20 65 / 50 删除50后 41 / \ 20 652.2 情况二删除只有一个子节点的节点需要将被删除节点的子节点提升到其原有位置。操作步骤定位到待删除节点用其唯一子节点替换自身释放节点内存可视化示例删除前 41 / \ 20 65 / 50 删除65后 41 / \ 20 502.3 情况三删除有两个子节点的节点最复杂的情况需要找到合适的替代节点来保持BST性质。通常有两种策略后继替换法用右子树的最小节点中序后继替换前驱替换法用左子树的最大节点中序前驱替换标准操作流程以后继替换为例找到待删除节点在其右子树中找到最小值节点最左节点用该最小值替换待删除节点的值递归删除右子树中的那个最小值节点可视化示例删除前 41 / \ 20 65 / \ 50 72 / \ 45 55 删除65后用72替换 41 / \ 20 72 / \ 50 72 / \ 45 553. 递归实现方案详解递归实现更直观地反映了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关键区别点需要显式维护parent指针删除操作分为搜索和修改两个独立阶段处理后继节点时需考虑其是否为右子树的直接根节点5. 边界条件与易错点分析在实际编码面试中以下边界条件经常被忽视删除根节点需要特殊处理parent为None的情况重复值标准BST通常不允许重复值但某些变体允许内存管理C等语言需要手动释放节点内存空树处理删除操作在空树上应安全返回节点不存在应保持树结构不变常见错误模式# 错误示例未正确处理parent指针 def deleteNodeWrong(root, key): if not root: return None # ...找到节点后直接修改... node.val successor.val # 只修改了值未更新树结构 return root6. 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指针深度不可预测的大树工程实践建议在内存受限环境优先选择迭代实现递归实现更易于维护和调试考虑使用线索二叉树优化中序后继查找对于频繁删除的场景建议使用平衡二叉搜索树8. 高级变种与扩展思考带父指针的BST简化了迭代实现中parent的维护懒惰删除标记节点为已删除而非立即移除适合频繁更新的场景线程二叉树通过线索化加速中序前驱/后继查找支持重复值的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时才实际移除节点。
)
