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

大家好，我是吴师兄。

今天继续来学习《剑指Offer》系列的一道经典题目，依旧给出了非常详细的题解和精美的配图与动画。

一、题目描述

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

限制：

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

二、题目解析

这道题目首先得掌握以下基础概念：

• 1、二叉搜索树
• 2、中序遍历的递归写法

二叉搜索树是一棵有序的二叉树，它具有如下的性质：

• 1、若它的左子树不为空，那么左子树上的所有值均小于它的根节点
• 2、若它的右子树不为空，那么右子树上所有值均大于它的根节点
• 3、它的左子树和右子树也都是二叉搜索树

而中序遍历的递归过程是 左 ---》根 ---》右 的顺序。

所以，如果对二叉搜索树采取中序遍历的方式，那么得到的序列是一个从小到大排列的递增序列，而如果采取中序遍历的倒序方式，那么得到的就是一个从大到小的递减序列。

因此，求二叉搜索树的第 k 大节点就可以转换为二叉搜索树的中序遍历的倒序方式的第 k 个节点。

具体操作如下：

1、设置两个全局变量，res 用来存储最后的那个节点的值，count 用来统计记录了第几大的节点，一开始为第零大。

2、接下来对二叉搜索树采取中序遍历的倒序方式，即按照 右 ---》根 —》左 的递归顺序。

3、在递归的过程中，如果发现 count == k，说明已经找到了目标节点，返回结果就行

4、否则需要不断的执行 count++ 操作，直到 count == k 位置，这样当前这个节点的值就是结果，赋值给 res 返回就行

为了帮助你更好的理解整个过程，我特意做了一组动画，点开可以查看：

三、参考代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 剑指 Offer 54. 二叉搜索树的第k大节点：https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof/
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 cur,int k) {

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

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

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

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

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