企业官网建设流程全解析

企业网站开发创意,什么网页游戏最火,优秀网页设计作品案例欣赏,网站开发合同售后服务文章目录摘要描述题解答案#xff08;整体思路#xff09;第一步#xff1a;找到要删除的节点第二步#xff1a;根据节点的结构分类处理题解代码#xff08;Swift 可运行 Demo#xff09;题解代码分析1. 为什么删除一定要分类讨论#xff1f;2. 叶子节点的删除3. 只有一…文章目录摘要描述题解答案整体思路第一步找到要删除的节点第二步根据节点的结构分类处理题解代码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→ 找到了开始处理删除逻辑第二步根据节点的结构分类处理找到目标节点后分三种情况叶子节点没有子节点直接删除返回nil只有一个子节点用它的子节点顶替它的位置左右子节点都存在找到右子树中的最小节点或左子树中的最大节点用这个值替换当前节点再递归删除被“借用”的那个节点这三种情况是整个题目的核心。题解代码Swift 可运行 Demo下面是完整的 Swift 实现包括TreeNode定义和删除逻辑。importFoundationpublicclassTreeNode{publicvarval:Intpublicvarleft:TreeNode?publicvarright:TreeNode?publicinit(_val:Int){self.valvalself.leftnilself.rightnil}}classSolution{funcdeleteNode(_root:TreeNode?,_key:Int)-TreeNode?{guardletrootrootelse{returnnil}ifkeyroot.val{root.leftdeleteNode(root.left,key)}elseifkeyroot.val{root.rightdeleteNode(root.right,key)}else{// 找到要删除的节点// 情况 1没有左子树ifroot.leftnil{returnroot.right}// 情况 2没有右子树ifroot.rightnil{returnroot.left}// 情况 3左右子树都存在letminNodefindMin(root.right)root.valminNode.val root.rightdeleteNode(root.right,minNode.val)}returnroot}privatefuncfindMin(_node:TreeNode?)-TreeNode{varcurrentnodewhilecurrent?.left!nil{currentcurrent?.left}returncurrent!}}题解代码分析1. 为什么删除一定要分类讨论因为 BST 的结构不统一删除节点后必须保证中序遍历仍然是有序的父子关系不能乱如果不分情况直接暴力删很容易破坏 BST 的结构。2. 叶子节点的删除ifroot.leftnilroot.rightnil{returnnil}这是最简单的一种情况直接删掉即可。在递归结构中其实可以合并到ifroot.leftnil{returnroot.right}因为root.right本身就是nil。3. 只有一个子节点的情况ifroot.leftnil{returnroot.right}ifroot.rightnil{returnroot.left}这种情况下用子节点直接“顶上来”不会破坏 BST 的规则。4. 左右子树都存在时怎么处理这是最关键、也最容易写错的部分。正确做法是找一个能替换当前节点又不破坏 BST 的值这个值只能来自右子树的最小值中序遍历的后继或左子树的最大值中序遍历的前驱本题中我们选的是右子树最小节点。letminNodefindMin(root.right)root.valminNode.val root.rightdeleteNode(root.right,minNode.val)这一步的本质是用后继节点的值覆盖当前节点再把那个后继节点删掉5. 为什么时间复杂度是 O(h)因为每次递归只往左或右走没有遍历整棵树最坏情况是树退化成链表高度为h示例测试及结果我们用示例 1 来跑一遍letrootTreeNode(5)root.leftTreeNode(3)root.rightTreeNode(6)root.left?.leftTreeNode(2)root.left?.rightTreeNode(4)root.right?.rightTreeNode(7)letsolutionSolution()letnewRootsolution.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 的性质能帮我们缩小问题范围