企业官网建设流程全解析

• 文档
• 教程
• 知识库

本篇文章以 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 count=0,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; stack<TreeNode*>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 小的元素，两道题可以放在一起对照学习：

在 230 题题解 中，仓库提供了三种写法，与本题形成了完整的"套路闭环"：

1. BFS 全收集 + map 排序（笨方法）：先层序遍历收集全部节点值再排序取第 k 个，时间复杂度高，仓库明确标注"太慢"，仅作反面教材；
2. 中序遍历迭代模板：root = root->left深入、出栈后转向root->right，计数到 k 即返回，与本题解法三镜像对称；
3. 中序遍历递归：int& k递减 +int& ans收集结果，与本题解法二镜像对称。

两道题合在一起正好覆盖"第 k 小 / 第 k 大"两种问法，无论面试官从哪个角度发问，都能用同一套模板快速作答。

进阶思考：230 题的进阶要求是——"如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化？"。这个进阶同样适用于本题：当"查询频繁 + 树频繁增删"时，可以在TreeNode中额外维护左子树节点个数（对应第 k 小）或右子树节点个数（对应第 k 大），将每次查询从 O(n) 降为 O(h)；配合平衡化（如 AVL 树）可进一步稳定在 O(log n)。这属于面试加分项，可在讲完上述三种基础解法后补充。

小结

回到这道题的三种解法，可以提炼出一条可复用的解题主线：

1. 识别 BST：看到"二叉搜索树 + 第 k 大/小"的组合，立刻联想到中序遍历的有序性；
2. 确定方向：第 k 大用"右 → 根 → 左"，第 k 小用"左 → 根 → 右"；
3. 选择实现：递归（全局计数器 / 引用参数递减）思路清晰适合口头讲解，迭代模板（显式栈）性能更稳、无递归溢出风险；
4. 命中即返：计数到 k 立即返回，避免无谓的整树遍历。

想要继续刷透树专题，可以参考仓库的 树专题目录 以及 剑指 Offer 全集，把中序、前序、后序三种遍历模板练熟后再来挑战本专题的其余 medium 题目，例如 面试题 07. 重建二叉树 与 面试题 33. 二叉搜索树的后序遍历序列，它们同样建立在"遍历顺序 + BST 性质"这两个基本点上。

• 文档
• 教程
• 知识库