文档教程知识库【免费下载链接】InterviewGuide「InterviewGuide」是阿秀从校园-职场多年计算机自学过程的记录以及学弟学妹们计算机校招秋招经验总结文章的汇总包括但不限于C/C 、Golang、JavaScript、Vue、操作系统、数据结构、计算机网络、MySQL、Redis等学习总结坚持学习持续成长项目地址https://gitcode.com/forthespada/InterviewGuide点击查看免费下载本篇文章以 InterviewGuide 仓库中 剑指 Offer 54「二叉搜索树的第 k 大节点」题解 为主体展开系统讲解这道高频校招/社招面试题的三种 C 解法两种递归写法与一种基于遍历模板的迭代写法。读完本文你将掌握利用二叉搜索树BST中序遍历有序性求解第 k 大/第 k 小元素的核心套路并能把同一套模板迁移到 230. 二叉搜索树中第 K 小的元素 等兄弟题目上。题目回顾找出二叉搜索树中第 k 大的节点原题链接LeetCode 剑指 Offer 54. 二叉搜索树的第k大节点题目描述给定一棵二叉搜索树请找出其中第 k 大的节点。示例 1输入: root [3,1,4,null,2], k 1 3 / \ 1 4 \ 2 输出: 4示例 2输入: root [5,3,6,2,4,null,null,1], k 3 5 / \ 3 6 / \ 2 4 / 1 输出: 4限制1 ≤ k ≤ 二叉搜索树元素个数即 k 恒有效无需额外判空。本题是 树专题目录 下 medium 难度中极具代表性的一题其价值在于它不考察任何花哨的数据结构而是直接考察对BST 性质 遍历顺序的理解程度。核心思路BST 中序遍历的倒过来就是降序序列二叉搜索树有一个经典性质中序遍历左 → 根 → 右得到的是节点值的升序序列。因此求第k 小按左 → 根 → 右的顺序遍历第 k 个访问到的节点即是答案求第k 大把遍历顺序反过来按右 → 根 → 左的顺序遍历第 k 个访问到的节点即是答案。右 → 根 → 左本质上就是中序遍历的镜像逆中序 / 反向后序遍历所以本仓库题解将其命名为后序遍历递归写法三种解法全部围绕这一顺序展开。这正是本仓库在 94. 二叉树的中序遍历 与 145. 二叉树的后序遍历 两篇文档中反复强调的遍历模板思想先确定遍历顺序再在访问节点处做业务处理。仓库中解法的TreeNode结构形如见 剑指 Offer 题解中的结构定义struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } };下面逐一看三种解法。解法一递归写法全局计数器版思路递归按右 → 根 → 左的顺序遍历。维护一个全局计数器count每当访问一个节点即处理根节点值时计数加一当count k时当前节点就是第 k 大的节点记录结果并返回。class Solution { public: int count0,result 0; void kthLargestCore(TreeNode* root, int k) { if (root nullptr) return ; if (root-right) kthLargestCore(root-right, k); count; if (count k) { result root-val; return; } if (root-left) kthLargestCore(root-left, k); return; } int kthLargest(TreeNode* root, int k) { kthLargestCore(root, k); return result;; } };该解法在原文档中记录的执行表现为执行用时 32 ms击败 62.54% 的用户内存消耗 24.3 MB击败 100.00% 的用户LeetCode C 提交数据。要点拆解count放在右子树递归完成之后、左子树递归开始之前精确对应访问根节点这一时机保证计数顺序就是右 → 根 → 左由于 k 恒有效1 ≤ k ≤ 元素个数result最终必然被赋值一旦count k便直接return提前剪枝无需遍历完整棵树这是优于全部遍历再取第 k 个的关键。解法二递归写法引用递减 k 版思路在解法一基础上做了一点改进——去掉独立的计数器count直接对引用参数k做递减。每访问一个节点就k--当k减到 0 时当前节点即为第 k 大的节点。class Solution { public: int result 0; void kthLargestCore(TreeNode* root, int k) { if (root nullptr) return ; if (root-right) kthLargestCore(root-right, k); k--; if (k 0) { result root-val; return; } if (root-left) kthLargestCore(root-left, k); return; } int kthLargest(TreeNode* root, int k) { kthLargestCore(root, k); return result;; } };要点拆解k必须用引用int k传递才能让递归栈内各层共享同一个递减变量若按值传递每层递归拿到的是副本k 0的判断将永远无法跨层生效这种参数即计数器的写法省去了成员变量count逻辑更紧凑是面试时容易口头讲清的版本与解法一相比两者遍历顺序完全相同只是计数方式不同一个用全局变量自增一个用引用参数自减。解法三迭代模板写法基于栈思路不使用递归改用显式栈模拟右 → 根 → 左的遍历过程。这是本仓库 94. 二叉树的中序遍历 与 145. 二叉树的后序遍历 中总结出的迭代遍历模板的直接应用while( 栈非空 || p 非空) { if( p 非空) { // 入栈并继续深入 } else { // 出栈并访问再转向另一侧 } }对于本题只需把模板中的向左深入改为向右深入、出栈后转向左子树即可int kthLargest(TreeNode* root, int k) { if (root nullptr) return 0; int count 0; stackTreeNode*s; while (!s.empty() || root ! nullptr) { if (root ! nullptr) { s.push(root); root root-right; } else { root s.top(); s.pop(); k--; if (k 0) return root-val; root root-left; } } return 0; }该解法在原文档中记录的执行表现为执行用时 28 ms击败 80.90% 的用户内存消耗 24.1 MB击败 100.00% 的用户LeetCode C 提交数据是三种写法中表现最好的一版。要点拆解root root-right对应先遍历右子树root root-left对应右子树处理完后再转向左子树与递归版本的顺序完全一致出栈即访问节点此时k--并判断是否归零命中即return root-val同样具备提前终止能力迭代写法不依赖系统递归栈避免了递归过深可能导致的栈溢出风险在链表化高度为 n的极端 BST 上更安全最坏情况下始终未命中前已遍历完整棵树时间复杂度为 O(n)空间复杂度为 O(h)h 为树高最坏 O(n)而由于 k 恒有效且命中即返回实际遍历节点数约等于 k 个大值节点的搜索路径远小于整棵树规模。兄弟题目一题两吃第 k 小即第 k 大的镜像仓库的同一目录下收录了它的镜像题目 230. 二叉搜索树中第 K 小的元素两道题可以放在一起对照学习题目遍历顺序命中条件二叉搜索树的第 k 大节点本题右 → 根 → 左第 k 个访问节点二叉搜索树中第 K 小的元素230 题左 → 根 → 右第 k 个访问节点在 230 题题解 中仓库提供了三种写法与本题形成了完整的套路闭环BFS 全收集 map 排序笨方法先层序遍历收集全部节点值再排序取第 k 个时间复杂度高仓库明确标注太慢仅作反面教材中序遍历迭代模板root root-left深入、出栈后转向root-right计数到 k 即返回与本题解法三镜像对称中序遍历递归int k递减 int ans收集结果与本题解法二镜像对称。两道题合在一起正好覆盖第 k 小 / 第 k 大两种问法无论面试官从哪个角度发问都能用同一套模板快速作答。进阶思考230 题的进阶要求是——如果二叉搜索树经常被修改插入/删除操作并且你需要频繁地查找第 k 小的值你将如何优化。这个进阶同样适用于本题当查询频繁 树频繁增删时可以在TreeNode中额外维护左子树节点个数对应第 k 小或右子树节点个数对应第 k 大将每次查询从 O(n) 降为 O(h)配合平衡化如 AVL 树可进一步稳定在 O(log n)。这属于面试加分项可在讲完上述三种基础解法后补充。小结回到这道题的三种解法可以提炼出一条可复用的解题主线识别 BST看到二叉搜索树 第 k 大/小的组合立刻联想到中序遍历的有序性确定方向第 k 大用右 → 根 → 左第 k 小用左 → 根 → 右选择实现递归全局计数器 / 引用参数递减思路清晰适合口头讲解迭代模板显式栈性能更稳、无递归溢出风险命中即返计数到 k 立即返回避免无谓的整树遍历。想要继续刷透树专题可以参考仓库的 树专题目录 以及 剑指 Offer 全集把中序、前序、后序三种遍历模板练熟后再来挑战本专题的其余 medium 题目例如 面试题 07. 重建二叉树 与 面试题 33. 二叉搜索树的后序遍历序列它们同样建立在遍历顺序 BST 性质这两个基本点上。赞分享文档教程知识库【免费下载链接】InterviewGuide「InterviewGuide」是阿秀从校园-职场多年计算机自学过程的记录以及学弟学妹们计算机校招秋招经验总结文章的汇总包括但不限于C/C 、Golang、JavaScript、Vue、操作系统、数据结构、计算机网络、MySQL、Redis等学习总结坚持学习持续成长项目地址https://gitcode.com/forthespada/InterviewGuide点击查看免费下载相关推荐InterviewGuide 剑指 Offer 精讲No62 二叉搜索树的第 K 个节点中序遍历解法全解析InterviewGuide 剑指 Offer 精讲No62 二叉搜索树的第 K 个节点中序遍历解法全解析 本文是《带你快速刷完 67 道剑指 Offer文档教程知识库如何上手 CyberStrikeAI从启动到第一个安全扫描任务的10分钟如何上手 CyberStrikeAI从启动到第一个安全扫描任务的10分钟 CyberStrikeAI 是一个 AI 原生安全测试平台你用一句话写下测试目标教程剑指 Offer No62二叉搜索树的第 K 个节点中序遍历的三种解法与进阶变体全剖析剑指 Offer No62二叉搜索树的第 K 个节点中序遍历的三种解法与进阶变体全剖析 本篇文章是 InterviewGuide 仓库《带你快速刷完 67教程创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考