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

文章目录

• • 摘要
  • 描述
  • 题解答案（整体思路）
  • • 第一步：找到要删除的节点
    • 第二步：根据节点的结构分类处理
  • 题解代码（Swift 可运行 Demo）
  • 题解代码分析
  • • 1. 为什么删除一定要分类讨论？
    • 2. 叶子节点的删除
    • 3. 只有一个子节点的情况
    • 4. 左右子树都存在时怎么处理？
    • 5. 为什么时间复杂度是 O(h)？
  • 示例测试及结果
  • 时间复杂度
  • 空间复杂度
  • 总结

摘要

在所有二叉搜索树（BST）的操作里，删除节点算是最容易让人写崩的一道题。

插入很好写，查找也没什么难度，但一到删除，就会遇到各种情况：

• 要删的节点是叶子节点怎么办
• 只有一个子节点怎么办
• 左右子树都存在又该怎么办

而这道 LeetCode 450，几乎把 BST 删除能遇到的所有坑都覆盖到了。

这篇文章会一步一步拆解 BST 删除节点的完整思路，用「分类讨论」的方式，把每一种情况都讲清楚，再给出一份可运行、好理解、好维护的 Swift 实现。

描述

题目要求我们：

• 给定一棵合法的二叉搜索树
• 给定一个要删除的值key
• 删除对应节点，并保持 BST 的性质不变
• 返回更新后的根节点

BST 的基本规则还是那一条：

• 左子树所有节点值 < 当前节点
• 右子树所有节点值 > 当前节点

同时题目还强调了一点：

要求算法时间复杂度为 O(h)，h 为树的高度

这其实在暗示我们：
不能把整棵树拍平重建，只能沿着搜索路径递归处理。

题解答案（整体思路）

删除 BST 节点，本质上可以拆成两步：

第一步：找到要删除的节点

这一点和普通 BST 查找完全一样：

• key < root.val→ 去左子树找
• key > root.val→ 去右子树找
• key == root.val→ 找到了，开始处理删除逻辑

第二步：根据节点的结构分类处理

找到目标节点后，分三种情况：

1. 叶子节点（没有子节点）

   • 直接删除，返回nil

2. 只有一个子节点

   • 用它的子节点顶替它的位置

3. 左右子节点都存在

   • 找到右子树中的最小节点（或左子树中的最大节点）
   • 用这个值替换当前节点
   • 再递归删除被“借用”的那个节点

这三种情况，是整个题目的核心。

题解代码（Swift 可运行 Demo）

下面是完整的 Swift 实现，包括TreeNode定义和删除逻辑。

importFoundationpublicclassTreeNode{publicvarval:Intpublicvarleft:TreeNode?publicvarright:TreeNode?publicinit(_val:Int){self.val=valself.left=nilself.right=nil}}classSolution{funcdeleteNode(_root:TreeNode?,_key:Int)->TreeNode?{guardletroot=rootelse{returnnil}ifkey<root.val{root.left=deleteNode(root.left,key)}elseifkey>root.val{root.right=deleteNode(root.right,key)}else{// 找到要删除的节点// 情况 1：没有左子树ifroot.left==nil{returnroot.right}// 情况 2：没有右子树ifroot.right==nil{returnroot.left}// 情况 3：左右子树都存在letminNode=findMin(root.right)root.val=minNode.val root.right=deleteNode(root.right,minNode.val)}returnroot}privatefuncfindMin(_node:TreeNode?)->TreeNode{varcurrent=nodewhilecurrent?.left!=nil{current=current?.left}returncurrent!}}

题解代码分析

1. 为什么删除一定要分类讨论？

因为 BST 的结构不统一，删除节点后，必须保证：

• 中序遍历仍然是有序的
• 父子关系不能乱

如果不分情况直接暴力删，很容易破坏 BST 的结构。

2. 叶子节点的删除

ifroot.left==nil&&root.right==nil{returnnil}

这是最简单的一种情况，直接删掉即可。

在递归结构中，其实可以合并到：

ifroot.left==nil{returnroot.right}

因为root.right本身就是nil。

3. 只有一个子节点的情况

ifroot.left==nil{returnroot.right}ifroot.right==nil{returnroot.left}

这种情况下，用子节点直接“顶上来”，不会破坏 BST 的规则。

4. 左右子树都存在时怎么处理？

这是最关键、也最容易写错的部分。

正确做法是：

• 找一个能替换当前节点，又不破坏 BST 的值

• 这个值只能来自：

  • 右子树的最小值（中序遍历的后继）
  • 或左子树的最大值（中序遍历的前驱）

本题中我们选的是：右子树最小节点。

letminNode=findMin(root.right)root.val=minNode.val root.right=deleteNode(root.right,minNode.val)

这一步的本质是：

• 用后继节点的值覆盖当前节点
• 再把那个后继节点删掉

5. 为什么时间复杂度是 O(h)？

因为：

• 每次递归只往左或右走
• 没有遍历整棵树
• 最坏情况是树退化成链表，高度为h

示例测试及结果

我们用示例 1 来跑一遍：

letroot=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)letsolution=Solution()letnewRoot=solution.deleteNode(root,3)print(newRoot?.val??-1)

删除3后，可能得到：

5 / \ 4 6 / \ 2 7

或另一种等价 BST 结构，都是正确结果。

时间复杂度

• 查找节点：O(h)
• 删除节点：O(h)

总体时间复杂度：O(h)
其中h是树的高度。

空间复杂度

• 递归调用栈占用：O(h)
• 没有使用额外的数据结构

空间复杂度：O(h)

总结

LeetCode 450 是一道非常典型、也非常值得反复消化的 BST 基础题。

它教会你的不是“怎么写删除”，而是：

• 如何用递归精确控制结构变化
• 如何通过分类讨论避免复杂度爆炸
• 为什么 BST 的性质能帮我们缩小问题范围