剑指 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 个节点还需在递归中实现三项工作递归遍历时计数统计当前节点的序号递归到第 k 个节点时记录结果res记录结果后后续的遍历即失去意义应提前终止即返回。按照递归的“终止条件—递归右子树—递推工作—递归左子树”结构展开终止条件当节点root为空越过叶节点直接返回递归右子树dfs(root.right)先访问所有更大的值递推工作访问当前节点时提前返回若k 0代表已找到目标节点无需继续遍历直接返回统计序号执行k k - 1把 k 从初值减到 0k 兼作“剩余还差几个节点”的计数器记录结果若减完后k 0说明当前节点正是第 k 大节点记录res root.val递归左子树dfs(root.left)访问更小的值通常在第 3 步已触发提前返回这行实际很少被执行到。注意k 0的提前返回放在“减一”之前它既是上一轮已经命中目标的标志也是让所有尚未展开的左子树分支快速剪枝的手段。这正是本算法平均只需访问O(k log N)量级节点的原因——命中目标后递归栈上残留的每一层都会因k 0立即返回不再向下展开。三语言完整实现题目指出1 ≤ k ≤ NN 为节点个数因此无需考虑k N的非法输入若考虑可以在遍历完成后判断k 0是否成立若成立则说明k N。Python对应 sfo_54_the_kth_largest_node_of_a_binary_search_tree_s1.pyclass 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.javaclass 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.cppclass 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、右孩子 41 的右孩子为 2。画出来就是3 / \ 1 4 \ 2按“右、根、左”倒序访问的序列是4 → 3 → 2 → 1k 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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考