LeetCode 剑指 Offer 54. 二叉搜索树的第k大节点

约 6 分钟
文章信息 14 个分类 6 个标签
分类
LeetCode CodeTop 简单 已解决 已掌握 20-50 字节跳动 微软 阿里巴巴 腾讯 猿辅导 虾皮 剑指 Offer 剑指 Offer（第 2 版）
标签
深度优先搜索 树 二叉树 二叉搜索树 中序遍历 二叉搜索树经典题
目录

题目描述

✅ 剑指 Offer 54. 二叉搜索树的第k大节点

image-20241107211921075

image-20250418232003330

image-20250418232033538

题意分析

输入一棵二叉搜索树和一个正整数 k，要求返回树中第 k 大节点的值，只要值本身，不需要返回节点或整个排名序列。

「二叉搜索树」这个约束是全题最强的信号：树里任意节点的左子树全部小于它、右子树全部大于它，所以按左根右的中序顺序访问节点，得到的值天然是严格升序的。换句话说，这棵树已经把「排序」这件事做完了，我们要做的只是从这条有序序列里取出正确的位置。

另一个必须先想清楚的点是「第 k 大」而不是第 k 小。升序序列里第 k 大位于倒数第 k 个位置，如果按升序去数，必须先知道节点总数 n，再去取第 n - k + 1 个，等于要遍历两遍。反过来，如果能让访问顺序变成从大到小，那么第 k 大就是「从头数的第 k 个」，一遍即可。

边界方面：题目保证 1 <= k <= n，也就是 k 一定落在树内，不必处理 k 越界返回什么；但节点值可能重复的题面变体要留意，本题按互不相同处理，排名即出现顺序。树可能退化成一条链（每个节点只有右孩子），此时树高等于节点数，递归深度是最坏情况，需要在复杂度里体现。

解法：反向中序遍历计数

核心思路

问题关键：BST 的中序遍历是升序，但题目要第 k 大。如果先遍历全部节点再从数组尾部取值，会多用 $O(n)$ 空间，也无法在找到答案后停止。

为什么选反向中序：把“左、根、右”改为“右、根、左”，访问顺序就从大到小。使用显式栈迭代遍历，每弹出一个节点就令 k--，k == 0 时当前值即为答案，无需统计节点总数或做下标换算。

不变量：每次沿当前右链压栈完成后，栈顶就是剩余节点中的最大值；已弹出的 t 个节点恰好是整棵树最大的 t 个。弹出节点后再转向它的左子树，因为左子树中的值都比它小，却大于更早祖先左侧尚未发现的节点。

正确性：由 BST 的大小关系，每次弹出的值严格递减，第 k 次弹出的节点必然是第 k 大。题目保证 k 合法，所以循环一定能在栈耗尽前返回。

解题步骤

  1. 从根开始沿右链压栈，直到当前节点为空。
  2. 弹出栈顶，这就是降序遍历的下一个节点；令 k--。
  3. 若 k == 0，立即返回当前节点值；否则转向它的左孩子。
  4. 重复“压入右链—弹栈访问—转向左子树”。

口述样例：BST [5,3,7,2,4,6,8] 的反向中序依次弹出 8、7、6...，所以 k = 3 时返回 6，其余更小节点不必访问。

代码实现

class Solution {
    public int kthLargest(TreeNode root, int k) {
        Deque<TreeNode> stack = new ArrayDeque<>();
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.right;
            }

            root = stack.pop();
            if (--k == 0) {
                return root.val;
            }
            root = root.left;
        }
        return -1;
    }
}

func kthLargest(root *TreeNode, k int) int {
    stack := make([]*TreeNode, 0)
    for root != nil || len(stack) > 0 {
        for root != nil {
            stack = append(stack, root)
            root = root.Right
        }

        root = stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        k--
        if k == 0 {
            return root.Val
        }
        root = root.Left
    }
    return -1
}

复杂度分析

  • 时间复杂度：$O(h + k)$。初始压入最右链最多走 h 层，之后访问前 k 个降序节点；最坏仍为 $O(n)$。
  • 空间复杂度：$O(h)$。显式栈最多保存一条根到叶路径；平衡树为 $O(\log n)$，退化树为 $O(n)$。

关键点总结

  • BST 的左根右中序为升序，右根左反向中序为降序；第 k 大直接数降序第 k 个。
  • k-- 必须发生在节点出栈时，因为出栈才表示真正访问了节点。
  • 找到答案立即返回，避免为了一个排名遍历整棵树。
  • 若要频繁查询第 k 大，可在节点中维护子树大小，使单次查询降为 $O(h)$；代价是更新树时同步维护计数。

易错点总结

  • 遍历方向写成左根右：样例树 k = 3 会返回第 3 小的 4，而不是第 3 大的 6。
  • 先访问节点再走右子树：会破坏降序顺序，最大值不再最先被计数。
  • 入栈时就递减 k：入栈只是发现节点，尚未完成右侧更大节点的访问，排名会提前。
  • 弹栈后忘记转向左孩子：会漏掉当前节点与其祖先之间的值。
  • 已采用降序遍历后又取第 n-k+1 个：发生二次换算，结果反而变成第 k 小。

相似题目

题目 难度 考察点
98. 验证二叉搜索树 中等 中序判严格递增，或上下界向下传递
230. 二叉搜索树中第 K 小的元素 中等 本题的镜像，左根右中序数第 k 个即第 k 小
426. 将二叉搜索树转化为排序的双向链表 中等 中序过程中记录前驱，原地改指针成循环双链表
538. 把二叉搜索树转换为累加树 中等 同样走右根左，但累加后缀和而非计数
897. 递增顺序搜索树 简单 中序重排成只有右孩子的单链树
1038. 从二叉搜索树到更大和树 中等 与 538 等价题面，反序中序前缀累加
LCR 052. 递增顺序搜索树 简单 897 的 LCR 版本，考察中序拼接时的断链处理
LCR 054. 把二叉搜索树转换为累加树 中等 538 的 LCR 版本，反序遍历中维护运行和
剑指 Offer 36. 二叉搜索树与双向链表 中等 426 的剑指版本，额外要求首尾相连
面试题 04.05. 合法二叉搜索树 中等 98 的等价题，注意相等值与整型边界
面试题 17.12. BiNode 简单 中序展开为右斜链，要求 $O(1)$ 额外空间原地做