企业官网建设流程全解析

剑指 Offer 54 详解：二叉搜索树的第 k 大节点——用反向中序遍历一步到位

【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C++ 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book

本篇基于 LeetCode-Book 仓库中《剑指 Offer》系列的第 54 题文档，讲解如何利用“二叉搜索树中序遍历为递增序列”这一性质，将“求第 k 大节点”转化为“反向中序遍历（右、根、左）取第 k 个节点”的递归问题。读完后，你将掌握反向中序遍历的构造方法、递归过程中的计数与提前终止技巧，并能直接复用仓库中 Python、Java、C++ 三语可运行的完整实现。

问题背景与核心性质

题目要求：给定一棵二叉搜索树（BST）的根节点root和一个整数k，请返回该树中第k大（注意，不是第 k 小）的节点值。题目约束1 ≤ k ≤ N，其中N为节点个数。

解法完全建立在一个基本性质之上：

二叉搜索树的中序遍历（左、根、右）得到的是递增序列。

这是 BST 定义（左子树所有值 < 根 < 右子树所有值）的直接推论。由此可以立刻得到它的对偶：

中序遍历的倒序（右、根、左）得到的是递减序列。

因此，“求第 k 大的节点”就等价于“按 右→根→左 的顺序遍历，取第 k 个访问到的节点”。这一点把问题从“排序后取下标”这种 O(N log N) 的思路，拉回到了 O(N) 的遍历思路，甚至配合提前终止后实际访问的节点数远少于 N。

中序遍历与中序遍历倒序的对照

先看标准的中序遍历递归模板，顺序是“左、根、右”：

# 打印中序遍历 def dfs(root): if not root: return dfs(root.left) # 左 print(root.val) # 根 dfs(root.right) # 右

// 打印中序遍历 void dfs(TreeNode root) { if(root == null) return; dfs(root.left); // 左 System.out.println(root.val); // 根 dfs(root.right); // 右 }

void dfs(TreeNode* root) { if(root == nullptr) return; dfs(root->left); cout << root->val; dfs(root->right); }

而本题需要的中序遍历倒序，只需把“左”与“右”的递归调用顺序对调，变成“右、根、左”：

# 打印中序遍历倒序 def dfs(root): if not root: return dfs(root.right) # 右 print(root.val) # 根 dfs(root.left) # 左

// 打印中序遍历倒序 void dfs(TreeNode root) { if(root == null) return; dfs(root.right); // 右 System.out.println(root.val); // 根 dfs(root.left); // 左 }

void dfs(TreeNode* root) { if(root == nullptr) return; dfs(root->right); cout << root->val; dfs(root->left); }

这个“对调左右递归调用”的技巧非常值得记忆：同一棵 BST，中序与反向中序的递归骨架只差一行调用顺序，分别对应第 k 小与第 k 大的查询。

递归解析：计数、记录与提前终止

只完成“按倒序打印”还不够，为求第 k 个节点，还需在递归中实现三项工作：

1. 递归遍历时计数，统计当前节点的序号；
2. 递归到第 k 个节点时，记录结果res；
3. 记录结果后，后续的遍历即失去意义，应提前终止（即返回）。

按照递归的“终止条件—递归右子树—递推工作—递归左子树”结构展开：

1. 终止条件：当节点root为空（越过叶节点），直接返回；
2. 递归右子树：dfs(root.right)，先访问所有更大的值；
3. 递推工作（访问当前节点时）：
   1. 提前返回：若k == 0，代表已找到目标节点，无需继续遍历，直接返回；
   2. 统计序号：执行k = k - 1（把 k 从初值减到 0，k 兼作“剩余还差几个节点”的计数器）；
   3. 记录结果：若减完后k == 0，说明当前节点正是第 k 大节点，记录res = root.val；
4. 递归左子树：dfs(root.left)，访问更小的值（通常在第 3 步已触发提前返回，这行实际很少被执行到）。

注意k == 0的提前返回放在“减一”之前：它既是上一轮已经命中目标的标志，也是让所有尚未展开的左子树分支快速剪枝的手段。这正是本算法平均只需访问O(k + log N)量级节点的原因——命中目标后，递归栈上残留的每一层都会因k == 0立即返回，不再向下展开。

三语言完整实现

题目指出1 ≤ k ≤ N（N 为节点个数），因此无需考虑k > N的非法输入；若考虑，可以在遍历完成后判断k > 0是否成立，若成立则说明k > N。

Python（对应 sfo_54_the_kth_largest_node_of_a_binary_search_tree_s1.py）：

class Solution: def kthLargest(self, root: TreeNode, k: int) -> int: def dfs(root): if not root: return dfs(root.right) if self.k == 0: return self.k -= 1 if self.k == 0: self.res = root.val dfs(root.left) self.k = k dfs(root) return self.res

这里k与res挂在self上（而非dfs的返回值），是为了让内部嵌套的dfs能在递归过程中直接读写共享状态；如果不想污染self，也可以用非局部变量或返回“访问计数”改写。

Java（对应 sfo_54_the_kth_largest_node_of_a_binary_search_tree_s1.java）：

class Solution { int res, k; public int kthLargest(TreeNode root, int k) { this.k = k; dfs(root); return res; } void dfs(TreeNode root) { if(root == null) return; dfs(root.right); if(k == 0) return; if(--k == 0) res = root.val; dfs(root.left); } }

C++（对应 sfo_54_the_kth_largest_node_of_a_binary_search_tree_s1.cpp）：

class Solution { public: int kthLargest(TreeNode* root, int k) { this->k = k; dfs(root); return res; } private: int res, k; void dfs(TreeNode* root) { if(root == nullptr) return; dfs(root->right); if(k == 0) return; if(--k == 0) res = root->val; dfs(root->left); } };

三处实现结构完全一致，差异仅在于作用域语法：Java 用this.k区分形参与成员变量，C++ 用--k前缀自减把“减一”与“判断是否归零”合并成一步。

仓库代码中的测试用例

Python 版文件自带一个可直接运行的 driver（测试代码）：

# ======= Test Case ======= root = list_to_tree([3, 1, 4, None, 2, None, None, None, None]) k = 1 # ====== Driver Code ====== slt = Solution() res = slt.kthLargest(root, k) print(res)

其中list_to_tree是仓库公共工具 binary_tree.py 中定义的层序建树函数：它把列表[3, 1, 4, None, 2, ...]按层序还原成二叉树——根为 3，左孩子 1、右孩子 4，1 的右孩子为 2。画出来就是：

3 / \ 1 4 \ 2

按“右、根、左”倒序访问的序列是4 → 3 → 2 → 1，k = 1时第一个访问到的就是 4，程序输出4。C++ 与 Java 版的main函数使用同一个逻辑测试用例（C++ 中以INT_MAX代替null占位空节点，见 C++ TreeNode 工具 中vectorToTree的约定；Java 中用TreeNode.arrToTree建树），同样验证输出为 4。

顺带一提，若把k换成 2，倒序序列的第 2 个值是 3；换成 3 则是 2——可以自行修改k验证算法对任意k都成立。

复杂度分析

• 时间复杂度 O(N)：最坏情况是树退化为一条链表（例如全部为右子节点），此时无论k取何值，都要沿链走到底才能确定第 k 大，递归深度与访问时间均为O(N)。平均情况下由于提前终止，实际访问节点数远小于 N。
• 空间复杂度 O(N)：同样是退化情形，系统递归栈的深度达到O(N)。对高度平衡的 BST，则降为O(log N)。

小结与延伸

本题的完整思路链条可以浓缩为一句话：BST 的中序遍历是有序序列 → 要第 k 大就用“右、根、左”反向中序 → 递归中用 k 作计数器，命中即提前返回剪枝。

掌握这个骨架后，可以自然延伸到仓库中几个相关题目：

• 求“第 k 小”的节点：只需把递归调用顺序改回标准中序（左、根、右），即 LeetCode-Book 中 230. 二叉搜索树中第 K 小的元素 一类的写法；
• 验证 BST 合法性：用中序遍历检查是否严格递增，对应 剑指 Offer 33. 二叉搜索树的后序遍历序列；
• 把 BST 原地串成有序双向链表：按中序（或其倒序）串联节点，见 剑指 Offer 36. 二叉搜索树与双向链表 与 426. 将二叉搜索树转化为排序的双向链表。

此外，若题目允许利用 BST 的有序性进一步优化（例如“第 k 小”可以从根节点逐层判断左子树规模、直接跳子树），可以把时间压到O(log N)；但在剑指 Offer 本题的约束下，反向中序遍历 + 计数剪枝已经是最简洁、最通用、也最贴合“遍历”主题的解法。

【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C++ 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book