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

大家好，我是程序员吴师兄，欢迎来到 图解剑指 Offer 结构化专栏，在这个专栏里我将和大家一起学习如何用结构化的思维来思考、解题、写代码，希望能帮助你即使在面试的时候紧张也能做对。

AlgoMooc 算法慕课网，每道题目都有动画和图片，致力于帮助每个程序员通过算法面试！

今天分享的题目来源于 LeetCode 上的剑指 Offer 系列面试题54. 二叉搜索树的第k大节点。

题目汇总链接：https://www.algomooc.com/jianzhioffer

一、题目描述

给定一棵二叉搜索树，请找出其中第 k 大的节点。

限制：

• 1 ≤ k ≤ 二叉搜索树元素个数

二、题目解析

这道题目考察的就是你对于二叉树的基础内容掌握的如何，首先要知道二叉搜索树的概念，它
是在二叉树的基础上添加了以下几个特点：

• 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；

• 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；

• 它的左、右子树也分别为二叉搜索树。

再者，要知道二叉树有四种遍历方式：前序遍历、中序遍历、后序遍历、层序遍历，并熟知这四种遍历方式的特点。

有了这两个基础，思路马上就有了：中序遍历二叉搜索树，最终得到的序列是递增有序的，只需要把所有节点存放到一个数组中，再从后向前数即可获取到第 K 到的节点。

这种思路代码很容易写出来，就不做详解了。

进一步思考，能否得到一个递减的有序序列，这样就无需存放所有的节点到数组中，只需要存放 K 个节点就得到结果。

可以的，中序遍历的倒序操作。

中序遍历的正常路程是左、根、右，那么它的倒序操作是右、根、左。

这样，每次遍历的节点都是当前二叉搜索树中最大的那个节点，利用一个全局变量 count 来统计目前已经更新到第几大的节点，当 count 和题目的 K 相等时就无需再去遍历二叉搜索树，已经获取到结果了。

三、动画描述

四、图片描述

五、参考代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
class Solution {
    // 设置全局变量 res，用来存储结果
    int res = 0 ;
    // 设置全局变量 count，用来表示记录了第几大的节点，默认是第零大
    int count = 0;

    public int kthLargest(TreeNode root, int k) {

        // 二叉搜索树中序遍历的倒序操作，最终会生成一个递减的有序序列
        helper(root,k);

        // 返回第 k 大的节点值
        return res;
    }

    void helper(TreeNode root,int k) {

        // 访问到空节点就无需再遍历了
        if(root == null) return;

        // 中序遍历的倒序操作从节点的右子节点开始
        helper(root.right,k);

        // 如果此时全局变量 count 已经等于 k ，说明已经获取到第 k 大的节点，无需再访问当前节点（根）的值，也无需继续遍历下去
        if(count == k ) return;

        // 否则更新全局变量 count 的值，并继续遍历下去
        count++;

        // 如果此时全局变量 count 已经等于 k ，说明已经获取到第 k 大的节点，无需再遍历下去，直接获取当前节点的值，赋值给 res
        if(count == k ) res = root.val;

        // 最后再访问当前节点的左子节点
        helper(root.left,k);
    }
}

六、复杂度分析

时间复杂度

时间复杂度为 O(N)。

空间复杂度

空间复杂度为 O(N)。

七、相关标签

• 深度优先搜索
• 二叉搜索树

程序员吴师兄算法训练营永久会员

收藏 海报 链接