绵阳市网站建设_网站建设公司_Ruby_seo优化

【LeetCode热题100】Java详解：二叉搜索树中第K小的元素（含进阶优化与面试延伸）

面向人群

• 正在准备技术面试（尤其是大厂算法岗、后端开发岗）的程序员
• 已掌握基础数据结构，希望深入理解二叉搜索树及其应用场景的学习者
• 对算法优化、平衡树、工程实践感兴趣的中级开发者
• 刷 LeetCode「热题100」或「二叉树专题」的用户

📌 本文适合具备一定 Java 编程能力和算法基础的读者。如果你刚接触递归或树结构，建议先完成 LeetCode 前50题中的基础二叉树题目。

关键词

LeetCode 230、二叉搜索树、BST、第K小元素、中序遍历、迭代遍历、子树节点数、AVL树、平衡二叉搜索树、Order Statistic Tree、时间复杂度优化、高频查询优化、面试高频题

阅读前必须掌握的基础

在深入阅读本文前，请确保你已熟练掌握以下知识点：

1. 二叉树的基本概念

   • 节点、根、叶子、深度、高度
   • 递归与树的遍历思想

2. 二叉搜索树（BST）的定义与性质

   • 左子树所有节点 < 根节点 < 右子树所有节点
   • 中序遍历结果为升序序列

3. 三种基本遍历方式（前序、中序、后序）

   • 能手写递归和非递归（栈模拟）的中序遍历
   • 理解遍历顺序与访问时机的关系

4. Java 基础语法与常用类

   • TreeNode结构（LeetCode 默认定义）
   • Deque/Stack的使用
   • HashMap的基本操作

5. 时间复杂度与空间复杂度分析

   • 能分析 O(log N)、O(N)、O(H) 等常见复杂度
   • 理解“最好/最坏/平均情况”的区别

6. （进阶部分可选）平衡树初步概念

   • 了解 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

提示：

• 树中的节点数为n
• 1 <= k <= n <= 10^4
• 0 <= 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 个访问的节点值。

三、答案构思：三种主流解法

我们将从基础 → 进阶 → 工程级优化三个层次展开：

下面逐一详解。

四、完整答案与代码实现（Java）

方法一：中序遍历（迭代版）—— 基础解法

思路

• 使用栈模拟递归，进行非递归中序遍历
• 每访问一个节点，k--
• 当k == 0时，当前节点即为答案，立即返回

✅ 优点：空间占用少，提前终止
❌ 缺点：每次查询都要重新遍历，无法复用

Java 代码

classSolution{publicintkthSmallest(TreeNoderoot,intk){Deque<TreeNode>stack=newArrayDeque<>();while(root!=null||!stack.isEmpty()){// 一路向左到底while(root!=null){stack.push(root);root=root.left;}// 弹出栈顶（当前最小未访问节点）root=stack.pop();k--;// 访问一个节点，k 减 1if(k==0){returnroot.val;// 找到第 k 小}// 转向右子树root=root.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){MyBstbst=newMyBst(root);returnbst.kthSmallest(k);}}classMyBst{TreeNoderoot;Map<TreeNode,Integer>nodeNum;// 节点 -> 子树大小publicMyBst(TreeNoderoot){this.root=root;this.nodeNum=newHashMap<>();countNodeNum(root);// 预处理：DFS 计算所有子树大小}publicintkthSmallest(intk){TreeNodenode=root;while(node!=null){intleftSize=getNodeNum(node.left);if(leftSize==k-1){returnnode.val;}elseif(leftSize<k-1){// 第 k 小在右子树k-=leftSize+1;node=node.right;}else{// 第 k 小在左子树node=node.left;}}return-1;}// DFS 后序遍历：先左右，再根privateintcountNodeNum(TreeNodenode){if(node==null)return0;intsize=1+countNodeNum(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;// 节点高度（叶子为 0）Node(intval,Nodeparent){this.val=val;this.parent=parent;this.size=1;this.height=0;}}Noderoot;// 构造函数：从有序列表构建平衡 BSTpublicAVL(List<Integer>vals){if(vals!=null&&!vals.isEmpty()){this.root=build(vals,0,vals.size()-1,null);}}// 分治构建平衡树privateNodebuild(List<Integer>vals,intl,intr,Nodeparent){if(l>r)returnnull;intmid=(l+r)/2;Nodenode=newNode(vals.get(mid),parent);node.left=build(vals,l,mid-1,node);node.right=build(vals,mid+1,r,node);recompute(node);// 更新 size 和 heightreturnnode;}// 查询第 k 小（与方法二逻辑一致）publicintkthSmallest(intk){Nodenode=root;while(node!=null){intleftSize=getSize(node.left);if(leftSize==k-1){returnnode.val;}elseif(leftSize<k-1){k-=leftSize+1;node=node.right;}else{node=node.left;}}return-1;}// 插入操作（略去旋转细节）publicvoidinsert(intv){// ... 标准 AVL 插入 + 旋转 + 更新 size/height}publicbooleandelete(intv){// ... 标准 AVL 删除 + 旋转 + 更新 size/height}// 辅助函数privatevoidrecompute(Nodenode){if(node==null)return;node.height=1+Math.max(getHeight(node.left),getHeight(node.right));node.size=1+getSize(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. 中序遍历得到有序列表List<Integer>list=newArrayList<>();inorder(root,list);// 2. 构建 AVL 树AVLavl=newAVL(list);// 3. 返回第 k 小returnavl.kthSmallest(k);}privatevoidinorder(TreeNodenode,List<Integer>list){if(node==null)return;inorder(node.left,list);list.add(node.val);inorder(node.right,list);}}

💡 实际工程中，可直接使用TreeSet（红黑树）或第三方库（如 Apache Commons Collections 的TreeList），但需自行维护 size 信息。

五、代码分析与对比

• H为树高，平衡时 H = log N，退化时 H = N
• 方法三虽复杂，但在数据库索引、排行榜系统等场景不可或缺

六、时间复杂度与空间复杂度深度分析

方法一：中序遍历

• 时间复杂度：O(H + k)
  • 最坏情况：树退化为链表（H = N），且 k = N → O(N)
  • 最好情况：平衡树（H = log N），k 很小 → 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）

✅优势：所有操作均为对数时间，适合高并发场景

七、常见问题解答（FAQ）

Q1：为什么中序遍历能得到升序序列？

A：由 BST 定义决定。中序 = 左 → 根 → 右，而左子树 < 根 < 右子树，递归展开即为升序。

Q2：能否用层序遍历或前序遍历？

A：不能。只有中序遍历能保证顺序性。前序/后序无法直接反映大小关系。

Q3：如果 BST 允许重复值怎么办？

A：需明确定义重复值的位置（如“左 ≤ 根 < 右”）。此时中序遍历仍有序，但第 K 小可能对应多个相同值。通常题目默认无重复。

Q4：方法二中为什么用 HashMap 而不修改 TreeNode？

A：LeetCode 的TreeNode是固定类，无法添加字段。实际开发中可自定义节点类，直接存储size字段。

Q5：AVL 树 vs 红黑树，哪个更适合？

A：

• AVL 更平衡（查询更快），但插入/删除旋转更多
• 红黑树更宽松（修改更快），广泛用于TreeMap、TreeSet
• 对于频繁查询第 K 小，AVL 略优（树高更低）

八、优化思路总结

💡 工程实践中，可结合缓存（如 LRU Cache）进一步优化热点查询。

九、数据结构与算法基础知识点回顾

9.1 二叉搜索树（BST）

• 定义：左 < 根 < 右
• 操作复杂度：查找/插入/删除 平均 O(log N)，最坏 O(N)
• 应用场景：字典、集合、排序

9.2 树的遍历方式

9.3 平衡二叉树（AVL）

• 平衡因子：左子树高 - 右子树高 ∈ {-1, 0, 1}
• 旋转类型：LL、RR、LR、RL
• 核心操作：insert→update height→check balance→rotate

9.4 复杂度分析技巧

• 最好/最坏/平均情况需分别讨论
• 摊还分析：适用于动态数组、哈希表等
• 主定理（Master Theorem）：用于分治算法

十、面试官提问环节（模拟）

Q：你提到 AVL 树，能手写一个右旋（Right Rotation）吗？

// 右旋：处理 LL 不平衡privateNoderotateRight(Nodey){Nodex=y.left;NodeT2=x.right;// 执行旋转x.right=y;y.left=T2;// 更新高度（先子后父）y.height=Math.max(getHeight(y.left),getHeight(y.right))+1;x.height=Math.max(getHeheight(x.left),getHeight(x.right))+1;// 更新 size（若维护）y.size=getSize(y.left)+getSize(y.right)+1;x.size=getSize(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 K

11.3 流数据中位数

• 维护两个堆（最大堆 + 最小堆）是常见解法
• 但若需任意分位数（如第 25% 小），BST 更灵活

11.4 文件系统目录大小统计

• 每个目录节点存储子目录数量/大小
• 类似方法二的size字段思想

十二、相关题目推荐

🔗 建议按此顺序刷题，形成知识闭环。

十三、总结与延伸

13.1 核心收获

• BST 的中序遍历 = 升序序列是解题钥匙
• 提前终止是优化遍历类问题的关键技巧
• 子树大小（size）是实现 Order Statistic 的基础
• 平衡树是动态场景的终极武器

13.2 延伸思考

• 分布式场景：如何在多机环境下维护全局第 K 小？
  • 方案：分片 + 各节点维护局部统计 + 归并
• 近似算法：若允许误差，能否用采样或 Sketch 技术？
  • 如 Count-Min Sketch、T-Digest
• 函数式编程：能否用惰性求值（Lazy Evaluation）实现中序遍历？
  • 如 Haskell 的 infinite list

13.3 终极建议

不要死记代码，要理解思想。
面试官想考察的不是你是否会写 AVL，而是：

• 能否从暴力解出发，逐步优化
• 能否权衡时间/空间/实现复杂度
• 能否联系实际工程场景

附录：完整 AVL 实现（供参考）

由于篇幅限制，此处省略完整 AVL 代码。完整实现包含：

• subtreeSearch
• rebalance
• restructure（trinode restructuring）
• rotate
• delete的复杂情况处理

可在 GitHub 搜索 “AVL Tree with size” 获取开源实现。

原创不易，欢迎点赞、收藏、评论！
关注我，获取更多 LeetCode 热题深度解析！