企业官网建设流程全解析

网站公司苏州,广州哪里有学做网站的,为网站做安全认证服务,中信建设网站【LeetCode热题100】Java详解#xff1a;二叉搜索树中第K小的元素#xff08;含进阶优化与面试延伸#xff09; 面向人群 正在准备技术面试#xff08;尤其是大厂算法岗、后端开发岗#xff09;的程序员已掌握基础数据结构#xff0c;希望深入理解二叉搜索树及其应用场…【LeetCode热题100】Java详解二叉搜索树中第K小的元素含进阶优化与面试延伸面向人群正在准备技术面试尤其是大厂算法岗、后端开发岗的程序员已掌握基础数据结构希望深入理解二叉搜索树及其应用场景的学习者对算法优化、平衡树、工程实践感兴趣的中级开发者刷 LeetCode「热题100」或「二叉树专题」的用户 本文适合具备一定 Java 编程能力和算法基础的读者。如果你刚接触递归或树结构建议先完成 LeetCode 前50题中的基础二叉树题目。关键词LeetCode 230、二叉搜索树、BST、第K小元素、中序遍历、迭代遍历、子树节点数、AVL树、平衡二叉搜索树、Order Statistic Tree、时间复杂度优化、高频查询优化、面试高频题阅读前必须掌握的基础在深入阅读本文前请确保你已熟练掌握以下知识点二叉树的基本概念节点、根、叶子、深度、高度递归与树的遍历思想二叉搜索树BST的定义与性质左子树所有节点 根节点 右子树所有节点中序遍历结果为升序序列三种基本遍历方式前序、中序、后序能手写递归和非递归栈模拟的中序遍历理解遍历顺序与访问时机的关系Java 基础语法与常用类TreeNode结构LeetCode 默认定义Deque/Stack的使用HashMap的基本操作时间复杂度与空间复杂度分析能分析 O(log N)、O(N)、O(H) 等常见复杂度理解“最好/最坏/平均情况”的区别进阶部分可选平衡树初步概念了解 AVL 树或红黑树的存在目的保持树高平衡知道“旋转”是维护平衡的手段不要求手写✅ 如果你对上述内容尚不熟悉建议先学习LeetCode 94二叉树的中序遍历LeetCode 98验证二叉搜索树《算法导论》第12章二叉搜索树在 LeetCode 的「热题 100」中“二叉搜索树中第 K 小的元素”是一道极具代表性的二叉树题目。它不仅考察了对二叉搜索树BST性质的理解还涉及中序遍历、递归/迭代实现、数据结构优化等多个核心知识点。更重要的是该题在面试中常被用作引子延伸出关于动态维护、平衡树、工程实践等高阶问题。本文将从原题回顾出发逐步深入到多种解法实现、复杂度分析、面试问答、实际应用及延伸思考力求打造一篇9000字的高质量技术博客帮助读者彻底掌握这道经典题目。一、原题回顾题目链接230. 二叉搜索树中第K小的元素题目描述给定一个二叉搜索树的根节点root和一个整数k请你设计一个算法查找其中第k小的元素k从 1 开始计数。示例 1输入root [3,1,4,null,2], k 1 输出1示例 2输入root [5,3,6,2,4,null,null,1], k 3 输出3提示树中的节点数为n1 k n 10^40 Node.val 10^4进阶问题如果二叉搜索树经常被修改插入/删除操作并且你需要频繁地查找第k小的值你将如何优化算法二、原题分析2.1 二叉搜索树BST的核心性质要解决本题首先必须深刻理解二叉搜索树的定义对于任意节点node其左子树中所有节点的值严格小于node.val其右子树中所有节点的值严格大于node.val左右子树本身也必须是二叉搜索树⚠️ 注意本题中未说明是否允许重复值。根据 LeetCode 测试用例通常假设 BST 中无重复值或即使有也按“左 ≤ 根 右”处理。但进阶部分会讨论允许重复的情况。2.2 第 K 小元素的含义在有序序列中“第 K 小”即升序排列后的第 K 个元素。例如[1,2,3,4,5]中第 3 小是3。而 BST 的一个关键特性是中序遍历In-order Traversal的结果是一个升序序列。因此问题转化为对 BST 进行中序遍历返回第 K 个访问的节点值。三、答案构思三种主流解法我们将从基础 → 进阶 → 工程级优化三个层次展开方法核心思想适用场景是否支持频繁查询方法一中序遍历迭代利用 BST 中序升序遍历到第 K 个即停一次性查询❌方法二预存子树节点数每个节点记录其子树大小支持 O(H) 查询多次查询树静态✅静态方法三平衡 BSTAVL动态维护平衡 子树大小支持高效增删查高频动态操作✅✅✅下面逐一详解。四、完整答案与代码实现Java方法一中序遍历迭代版—— 基础解法思路使用栈模拟递归进行非递归中序遍历每访问一个节点k--当k 0时当前节点即为答案立即返回✅ 优点空间占用少提前终止❌ 缺点每次查询都要重新遍历无法复用Java 代码classSolution{publicintkthSmallest(TreeNoderoot,intk){DequeTreeNodestacknewArrayDeque();while(root!null||!stack.isEmpty()){// 一路向左到底while(root!null){stack.push(root);rootroot.left;}// 弹出栈顶当前最小未访问节点rootstack.pop();k--;// 访问一个节点k 减 1if(k0){returnroot.val;// 找到第 k 小}// 转向右子树rootroot.right;}return-1;// 理论上不会执行到这里}}关键点解析为什么用迭代而不是递归递归虽然简洁但无法在找到答案后立即停止整个递归过程除非抛异常或使用全局变量。迭代可以自然 break。栈的作用模拟函数调用栈保存“待回溯”的父节点。方法二预计算子树节点数 —— 静态优化思路预处理为每个节点计算其子树总节点数包括自身查询时利用 BST 性质 子树大小直接跳过不需要的子树具体逻辑设当前节点为node其左子树节点数为leftSize若leftSize k - 1→ 当前节点就是第 K 小若leftSize k - 1→ 第 K 小在右子树更新k k - leftSize - 1若leftSize k - 1→ 第 K 小在左子树继续向左✅ 优点单次查询仅需 O(H) 时间❌ 缺点插入/删除后需重新计算子树大小成本高Java 代码classSolution{publicintkthSmallest(TreeNoderoot,intk){MyBstbstnewMyBst(root);returnbst.kthSmallest(k);}}classMyBst{TreeNoderoot;MapTreeNode,IntegernodeNum;// 节点 - 子树大小publicMyBst(TreeNoderoot){this.rootroot;this.nodeNumnewHashMap();countNodeNum(root);// 预处理DFS 计算所有子树大小}publicintkthSmallest(intk){TreeNodenoderoot;while(node!null){intleftSizegetNodeNum(node.left);if(leftSizek-1){returnnode.val;}elseif(leftSizek-1){// 第 k 小在右子树k-leftSize1;nodenode.right;}else{// 第 k 小在左子树nodenode.left;}}return-1;}// DFS 后序遍历先左右再根privateintcountNodeNum(TreeNodenode){if(nodenull)return0;intsize1countNodeNum(node.left)countNodeNum(node.right);nodeNum.put(node,size);returnsize;}privateintgetNodeNum(TreeNodenode){returnnodeNum.getOrDefault(node,0);}}设计亮点使用HashMap存储子树大小避免修改原树结构countNodeNum采用后序遍历确保子节点信息先于父节点计算方法三平衡二叉搜索树AVL—— 动态优化进阶背景当 BST频繁被修改插入/删除且需要高频查询第 K 小时方法二的预处理成本过高每次修改可能需 O(N) 重建。解决方案使用自平衡 BST如 AVL 树 或 红黑树并在每个节点中维护子树大小size和高度height。AVL 树核心特性任意节点的左右子树高度差 ≤ 1插入/删除后通过旋转rotate自动恢复平衡树高始终为 O(log N)保证操作效率Java 实现简化版 AVL注完整 AVL 实现已超 LeetCode 范畴此处展示核心逻辑// 平衡二叉搜索树AVL支持重复值、维护 size 和 heightclassAVL{staticclassNode{intval;Nodeparent,left,right;intsize;// 以该节点为根的子树节点总数intheight;// 节点高度叶子为 0Node(intval,Nodeparent){this.valval;this.parentparent;this.size1;this.height0;}}Noderoot;// 构造函数从有序列表构建平衡 BSTpublicAVL(ListIntegervals){if(vals!null!vals.isEmpty()){this.rootbuild(vals,0,vals.size()-1,null);}}// 分治构建平衡树privateNodebuild(ListIntegervals,intl,intr,Nodeparent){if(lr)returnnull;intmid(lr)/2;NodenodenewNode(vals.get(mid),parent);node.leftbuild(vals,l,mid-1,node);node.rightbuild(vals,mid1,r,node);recompute(node);// 更新 size 和 heightreturnnode;}// 查询第 k 小与方法二逻辑一致publicintkthSmallest(intk){Nodenoderoot;while(node!null){intleftSizegetSize(node.left);if(leftSizek-1){returnnode.val;}elseif(leftSizek-1){k-leftSize1;nodenode.right;}else{nodenode.left;}}return-1;}// 插入操作略去旋转细节publicvoidinsert(intv){// ... 标准 AVL 插入 旋转 更新 size/height}publicbooleandelete(intv){// ... 标准 AVL 删除 旋转 更新 size/height}// 辅助函数privatevoidrecompute(Nodenode){if(nodenull)return;node.height1Math.max(getHeight(node.left),getHeight(node.right));node.size1getSize(node.left)getSize(node.right);}privatestaticintgetHeight(Nodenode){returnnode!null?node.height:-1;// 空节点高度为 -1}privatestaticintgetSize(Nodenode){returnnode!null?node.size:0;}// 旋转、rebalance 等函数略见文末完整代码}在 LeetCode 主函数中使用classSolution{publicintkthSmallest(TreeNoderoot,intk){// 1. 中序遍历得到有序列表ListIntegerlistnewArrayList();inorder(root,list);// 2. 构建 AVL 树AVLavlnewAVL(list);// 3. 返回第 k 小returnavl.kthSmallest(k);}privatevoidinorder(TreeNodenode,ListIntegerlist){if(nodenull)return;inorder(node.left,list);list.add(node.val);inorder(node.right,list);}} 实际工程中可直接使用TreeSet红黑树或第三方库如 Apache Commons Collections 的TreeList但需自行维护 size 信息。五、代码分析与对比维度方法一中序遍历方法二子树计数方法三AVL时间复杂度单次查询O(H k)O(H)O(log N)空间复杂度O(H)O(N)O(N)是否支持动态修改否否修改后需重建✅ 是实现难度⭐⭐⭐⭐⭐⭐⭐适用场景一次性查询静态树多次查询高频动态操作H为树高平衡时 H log N退化时 H N方法三虽复杂但在数据库索引、排行榜系统等场景不可或缺六、时间复杂度与空间复杂度深度分析方法一中序遍历时间复杂度O(H k)最坏情况树退化为链表H N且 k N → O(N)最好情况平衡树H log Nk 很小 → O(log N)空间复杂度O(H)栈最多存储从根到最左叶的路径方法二子树计数预处理时间O(N)遍历整棵树单次查询时间O(H)空间O(N)哈希表存储每个节点的 size⚠️ 若树被修改需重新运行countNodeNum成本 O(N)方法三AVL 树构建时间O(N)中序 分治建树插入/删除O(log N)旋转次数 ≤ 2查询O(log N)空间O(N)每个节点额外存储 size 和 height✅优势所有操作均为对数时间适合高并发场景七、常见问题解答FAQQ1为什么中序遍历能得到升序序列A由 BST 定义决定。中序 左 → 根 → 右而左子树 根 右子树递归展开即为升序。Q2能否用层序遍历或前序遍历A不能。只有中序遍历能保证顺序性。前序/后序无法直接反映大小关系。Q3如果 BST 允许重复值怎么办A需明确定义重复值的位置如“左 ≤ 根 右”。此时中序遍历仍有序但第 K 小可能对应多个相同值。通常题目默认无重复。Q4方法二中为什么用 HashMap 而不修改 TreeNodeALeetCode 的TreeNode是固定类无法添加字段。实际开发中可自定义节点类直接存储size字段。Q5AVL 树 vs 红黑树哪个更适合AAVL 更平衡查询更快但插入/删除旋转更多红黑树更宽松修改更快广泛用于TreeMap、TreeSet对于频繁查询第 K 小AVL 略优树高更低八、优化思路总结场景推荐方案只查一次方法一简单高效静态树多次查询方法二预处理 O(H) 查询动态树高频操作方法三AVL/红黑树 维护 size内存极度受限方法一空间 O(H) 最小需要支持重复值自定义比较器 允许重复的 BST 工程实践中可结合缓存如 LRU Cache进一步优化热点查询。九、数据结构与算法基础知识点回顾9.1 二叉搜索树BST定义左 根 右操作复杂度查找/插入/删除 平均 O(log N)最坏 O(N)应用场景字典、集合、排序9.2 树的遍历方式遍历顺序应用前序根→左→右复制树、序列化中序左→根→右BST 升序输出后序左→右→根释放内存、计算目录大小层序按层从左到右打印树形、最短路径9.3 平衡二叉树AVL平衡因子左子树高 - 右子树高 ∈ {-1, 0, 1}旋转类型LL、RR、LR、RL核心操作insert→update height→check balance→rotate9.4 复杂度分析技巧最好/最坏/平均情况需分别讨论摊还分析适用于动态数组、哈希表等主定理Master Theorem用于分治算法十、面试官提问环节模拟Q你提到 AVL 树能手写一个右旋Right Rotation吗// 右旋处理 LL 不平衡privateNoderotateRight(Nodey){Nodexy.left;NodeT2x.right;// 执行旋转x.righty;y.leftT2;// 更新高度先子后父y.heightMath.max(getHeight(y.left),getHeight(y.right))1;x.heightMath.max(getHeheight(x.left),getHeight(x.right))1;// 更新 size若维护y.sizegetSize(y.left)getSize(y.right)1;x.sizegetSize(x.left)getSize(x.right)1;returnx;// 新的子树根}Q如果 k 很大接近 n有没有优化空间A可以反向中序遍历右→根→左查找第(n - k 1)大减少遍历次数。但需先知道n成本 O(N)仅当k n/2时划算。Q如何在不修改树结构的情况下支持动态查询A可使用Order Statistic Tree顺序统计树即在红黑树基础上维护子树大小。Java 中无内置实现但可通过封装TreeMap 手动维护 size 实现。十一、实际开发中的应用场景11.1 数据库索引B 树BST 的多路扩展用于数据库索引“第 K 小” 对应LIMIT OFFSET 查询如分页11.2 实时排行榜游戏积分榜、电商销量榜需支持插入新用户、更新分数、查询 Top K11.3 流数据中位数维护两个堆最大堆 最小堆是常见解法但若需任意分位数如第 25% 小BST 更灵活11.4 文件系统目录大小统计每个目录节点存储子目录数量/大小类似方法二的size字段思想十二、相关题目推荐题号题目关联点94二叉树的中序遍历基础遍历98验证二叉搜索树BST 性质173二叉搜索树迭代器中序遍历封装272最近的二叉搜索树值 IIBST 双指针1382将二叉搜索树变平衡平衡化315计算右侧小于当前元素的个数BST 应用480滑动窗口中位数动态第 K 小 建议按此顺序刷题形成知识闭环。十三、总结与延伸13.1 核心收获BST 的中序遍历 升序序列是解题钥匙提前终止是优化遍历类问题的关键技巧子树大小size是实现 Order Statistic 的基础平衡树是动态场景的终极武器13.2 延伸思考分布式场景如何在多机环境下维护全局第 K 小方案分片 各节点维护局部统计 归并近似算法若允许误差能否用采样或 Sketch 技术如 Count-Min Sketch、T-Digest函数式编程能否用惰性求值Lazy Evaluation实现中序遍历如 Haskell 的 infinite list13.3 终极建议不要死记代码要理解思想。面试官想考察的不是你是否会写 AVL而是能否从暴力解出发逐步优化能否权衡时间/空间/实现复杂度能否联系实际工程场景附录完整 AVL 实现供参考由于篇幅限制此处省略完整 AVL 代码。完整实现包含subtreeSearchrebalancerestructuretrinode restructuringrotatedelete的复杂情况处理可在 GitHub 搜索 “AVL Tree with size” 获取开源实现。原创不易欢迎点赞、收藏、评论关注我获取更多 LeetCode 热题深度解析