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

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

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

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

一、题目描述

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

限制:

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

二、题目解析

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

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

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

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

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

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

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

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

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

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

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

三、动画描述

隐藏内容
  • 普通用户购买价格:5积分
  • 会员用户购买价格:免费
  • 永久会员用户购买价格:免费推荐

四、图片描述

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

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

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

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

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

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

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

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

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

五、参考代码

// 登录 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)。

七、相关标签

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

发表评论

邮箱地址不会被公开。 必填项已用*标注