二叉树刷题记(六-二叉搜索树的第k大节点)

简介: 二叉树刷题记(六-二叉搜索树的第k大节点)

前言

今天更新到了第七天,终于达到了更文第一关的要求 ,写文章费了不少的时间(小嘟本身就写的很慢,再加上我对文章的质量有一定的要求,所以就...),但是一想到更文奖励,我就又动力啦!!!哈哈哈。

小嘟还是会保证文章质量的,不会因为为了参加活动就发一些水文,觉得这样既浪费了读者的时间,也浪费了小嘟的时间,最后,文章没什么价值可言,这也是我不愿意看到的。

希望读者看完能有所收获。

今日,还是回到更新二叉树系列,文章不会很长,请读者耐心阅读。

注:本嘟是个算法渣渣,(面试的时候让写个非递归的后序遍历都没有写出来,唉),so,我写文章的目的是为了帮助那些想学习算法,但是算法题目看了之后依然很迷茫的读者,大神请绕过哦!

目的

  • 本文目的:小嘟带着读者做做二叉树相关的题目,然后小嘟把自己的感悟总结出来。
  • 之前已经带大家将二叉树的三种遍历算法都学完了(包括递归和非递归),不会的请滑到文章底部,小嘟在底部放着链接哦!


正文

  • 首先,还是先看题目


  • 题目描述,让我们找一个二叉搜索树的第K大节点,小嘟还是在放一张图,看图直观点


  • 这里有一个二叉树的名词,二叉搜索树,那么什么是二叉搜索树呢?
  • 小嘟叨叨时刻:二叉搜索树,小嘟的理解就是一个结点的左孩子小于它,它的右孩子大于它,故此,我们可以知道二叉搜索树有一个性质:一个结点的左子树的val都小于等于它,它的右子树的val都大于等于它


概念搞清楚了,那就好好分析题目


首先由题目的限制条件可以知道,root不是一个空树(因为它k的限制条件告诉我们它肯定能找到一个元素)

我们要找到第K大元素,那么我们就要先遍历二叉树?怎样遍历这是一个问题。仔细想想:要遍历而且要找到第K大元素,那么我们首先是不是要找到一个递增或递减的顺序呢?哦,悟了悟了!我们要找这样的一个顺序,要么递增,要么递减。

现在就该想想我们该用那种遍历方式呢?前序?中序?后序?想想它们的遍历顺序,再结合二叉树的性质,还有就是我们要找的是一个递增或者递减的顺序。

分析之后,我们选择了中序遍历,这是一个递增的顺序。(还有一种方法哦!不知道给起个什么名字,暂且叫我假中序遍历,哈哈哈)

直接看代码呗

  • 递归版的
var kthLargest = function(root, k) {
    let res=[];
    const Kmax = (root01)=>{
        if(root01 == null) return;
        Kmax(root01.left);
        res.push(root01.val);
        Kmax(root01.right)
    }
    Kmax(root);
    let length = res.length;
    return res [length-k];
};

  • 迭代版的
var kthLargest = function(root, k) {
    let res=[];
    let stack = [];
    while(root || stack.length ){
        while(root){
            stack.push(root);
            root = root.left;
        }
        let node = stack.pop();
        res.push(node.val);
        root = node.right;
    }
    let length = res.length;
    return res [length-k];
};


另一种方法
  • 我们的思路还是不变,还是要找一个有序的顺序,我们找的是一个递减的顺序。
  • 递归版的
var kthLargest = function(root, k) {
    let res=[];
    const Kmax = (root01)=>{
        if(root01 == null) return;
        Kmax(root01.right);
        res.push(root01.val);
        Kmax(root01.left)
    }
    Kmax(root);
    return res[k-1];
};

  • 迭代版的
 var kthLargest = function(root, k) {
    let res=[];
    let stack = [];
    while(root || stack.length ){
        if(res.length == k) return res[k-1];
        while(root){
            stack.push(root);
            root = root.right;
        }
        let node = stack.pop()
        res.push(node.val);
        root = node.left;
    }
    return res[k-1];
};

  • 啦啦啦,小嘟讲完啦,感觉还是二叉树问题离不开三种遍历方式,所以我们要做二叉树相关的题目,首先还是要掌握三种最基本的遍历顺序。
    溜啦溜啦...

结尾

  • 希望各位学习算法的朋友能够坚持下去,加油
  • 若有任何问题,欢迎下方留言,小嘟看到会第一时间回复的。
  • 创作不易,觉得还不错的,欢迎支持支持!
  • 多想多做多尝试,实在不会的话,直接看代码,用代码来理解。
相关文章
|
28天前
|
Java
手撸二叉树——AVL平衡二叉树
本文介绍了AVL平衡二叉树的基本概念和实现方法。首先回顾了二叉查找树在插入节点后的不平衡问题,然后详细讲解了四种旋转操作:左左单旋转、右右单旋转、左右双旋转和右左双旋转,以确保树的平衡。文章还提供了Java代码实现,包括节点插入、删除和平衡调整的具体方法。通过这些操作,AVL树能够保持较低的高度,从而提高查询性能。
20 0
|
6月前
二叉树刷题记(二-中序遍历)
二叉树刷题记(二-中序遍历)
|
6月前
二叉树刷题记(七-二叉树的右侧视图)
二叉树刷题记(七-二叉树的右侧视图)
|
6月前
二叉树刷题记(四-前序遍历)
二叉树刷题记(四-前序遍历)
|
6月前
|
算法
二叉树刷题记(三-后序遍历)
二叉树刷题记(三-后序遍历)
|
6月前
|
算法
二叉树刷题记(八-二叉树的最大深度-深度遍历)
二叉树刷题记(八-二叉树的最大深度-深度遍历)
|
6月前
二叉树刷题记(九-二叉搜索树中的中序后继-中序遍历)
二叉树刷题记(九-二叉搜索树中的中序后继-中序遍历)
|
6月前
二叉树刷题记(十-1.二叉树的镜像-2.二叉搜索树中的搜索)大家一起学习呗
二叉树刷题记(十-1.二叉树的镜像-2.二叉搜索树中的搜索)大家一起学习呗
|
6月前
[leedcode]刷题有感 二叉树的深度、节点数量、与平衡二叉树1
[leedcode]刷题有感 二叉树的深度、节点数量、与平衡二叉树
|
6月前
[leedcode]刷题有感 二叉树的深度、节点数量、与平衡二叉树2
[leedcode]刷题有感 二叉树的深度、节点数量、与平衡二叉树2