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

Categories:

题目描述
思路分析
1. 解法一：反向中序遍历（递归）（推荐）
2. 解法二：反向中序遍历（迭代）
相似题目

题目描述

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

思路分析

解法一：反向中序遍历（递归）（推荐）

核心思路：

BST 中序遍历（左→根→右）结果为升序序列

反向中序遍历（右→根→左）结果为降序序列

按降序依次访问节点，计数到第 k 个节点即为第 k 大值

找到目标后无需继续遍历，直接返回

复杂度分析：

时间复杂度：O(h + k)，其中 h 为树的高度，最坏情况下先走到最右叶子节点（O(h)），再回溯 k 个节点

空间复杂度：O(h)，递归调用栈的深度为树的高度

class Solution {
    // 计数器，记录当前访问的是第几大节点
    private int count;
    // 保存结果
    private int result;

    public int kthLargest(TreeNode root, int k) {
        count = k;
        inorder(root);
        return result;
    }

    // 反向中序遍历：右 → 根 → 左（降序）
    private void inorder(TreeNode node) {
        if (node == null) {
            return;
        }
        // 先遍历右子树（更大的值）
        inorder(node.right);
        // 计数到 k 时记录结果并终止
        count--;
        if (count == 0) {
            result = node.val;
            return;
        }
        // 再遍历左子树（更小的值）
        inorder(node.left);
    }
}

func kthLargest(root *TreeNode, k int) int {
    count := 0
    res := 0

    // 反向中序遍历：右 → 根 → 左（降序）
    var inorder func(node *TreeNode)
    inorder = func(node *TreeNode) {
        if node == nil {
            return
        }
        // 先遍历右子树（更大的值）
        inorder(node.Right)
        // 计数到 k 时记录结果
        count++
        if count == k {
            res = node.Val
            return
        }
        // 再遍历左子树（更小的值）
        inorder(node.Left)
    }

    inorder(root)
    return res
}

解法二：反向中序遍历（迭代）

核心思路：

使用显式栈模拟反向中序遍历（右→根→左）

每次弹出栈顶节点时计数，第 k 次即为答案

迭代写法避免了递归栈溢出风险，适合树高较大的场景

复杂度分析：

时间复杂度：O(h + k)，其中 h 为树的高度，先走到最右叶子节点，再访问 k 个节点

空间复杂度：O(h)，栈中最多存储树的高度个节点

class Solution {
    public int kthLargest(TreeNode root, int k) {
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode cur = root;

        while (cur != null || !stack.isEmpty()) {
            // 一路向右，将右侧节点全部压栈
            while (cur != null) {
                stack.push(cur);
                cur = cur.right;
            }
            // 弹出栈顶节点（当前最大的未访问节点）
            cur = stack.pop();
            // 计数，第 k 次即为答案
            k--;
            if (k == 0) {
                return cur.val;
            }
            // 转向左子树继续遍历
            cur = cur.left;
        }
        return -1;
    }
}

func kthLargest(root *TreeNode, k int) int {
    var stack []*TreeNode
    cur := root

    for cur != nil || len(stack) > 0 {
        // 一路向右，将右侧节点全部压栈
        for cur != nil {
            stack = append(stack, cur)
            cur = cur.Right
        }
        // 弹出栈顶节点（当前最大的未访问节点）
        cur = stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        // 计数，第 k 次即为答案
        k--
        if k == 0 {
            return cur.Val
        }
        // 转向左子树继续遍历
        cur = cur.Left
    }
    return -1
}

相似题目

题目	难度	考察点
230. 二叉搜索树中第 K 小的元素	中等	BST 中序遍历 / 迭代
94. 二叉树的中序遍历	简单	递归 / 迭代 / 中序遍历
98. 验证二叉搜索树	中等	BST 性质 / 中序遍历
173. 二叉搜索树迭代器	中等	BST 迭代器 / 中序遍历
285. 二叉搜索树中的中序后继	中等	BST 性质 / 中序遍历
538. 把二叉搜索树转换为累加树	中等	BST 反向中序遍历
1038. 从二叉搜索树到更大数值和	中等	BST 反向中序遍历

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2024/73632605