一、题目描述

给定一棵二叉搜索树,请找出其中第 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);
    }
}

2、C++ 代码

// 登录 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;
    }

private:
    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);
    }
};

3、Python 代码

class Solution:

    # 设置全局变量 res,用来存储结果
    res = 0 
    # 设置全局变量 count,用来表示记录了第几大的节点,默认是第零大
    count = 0

    def kthLargest(self, root: TreeNode, k: int) -> int:

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

        # 返回第 k 大的节点值
        return self.res

    def helper(self, cur: TreeNode, k: int):

        # 访问到空节点就无需再遍历了
        if not cur  : return

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

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

        # 否则更新全局变量 count 的值,并继续遍历下去
        self.count += 1

        # 如果此时全局变量 count 已经等于 k ,说明已经获取到第 k 大的节点,无需再遍历下去,直接获取当前节点的值,赋值给 res
        if self.count == k :   self.res = cur.val

        # 最后再访问当前节点的左子节点
        self.helper(cur.left,k)
声明:本站所有文章,如无特殊说明或标注,均为本站原创发布。任何个人或组织,在未征得本站同意时,禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。