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

发表于

这是我参与11月更文挑战的第7天，活动详情查看：2021最后一次更文挑战

前言

  • 今天更新到了第七天，终于达到了更文第一关的要求 ，写文章费了不少的时间（小嘟本身就写的很慢，再加上我对文章的质量有一定的要求，所以就...）,但是一想到更文奖励，我就又动力啦！！！哈哈哈。
  • 小嘟还是会保证文章质量的，不会因为为了参加活动就发一些水文，觉得这样既浪费了读者的时间，也浪费了小嘟的时间，最后，文章没什么价值可言，这也是我不愿意看到的。
  • 希望读者看完能有所收获。
  • 今日，还是回到更新二叉树系列，文章不会很长，请读者耐心阅读。
  • 注：本嘟是个算法渣渣，（面试的时候让写个非递归的后序遍历都没有写出来，唉），so，我写文章的目的是为了帮助那些想学习算法，但是算法题目看了之后依然很迷茫的读者，大神请绕过哦！

目的

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

正文

  • 首先，还是先看题目
    image.png
    image.png
  • 题目描述，让我们找一个二叉搜索树的第K大节点，小嘟还是在放一张图，看图直观点
    image.png
  • 这里有一个二叉树的名词，二叉搜索树，那么什么是二叉搜索树呢？
  • 小嘟叨叨时刻：二叉搜索树，小嘟的理解就是一个结点的左孩子小于它，它的右孩子大于它，故此，我们可以知道二叉搜索树有一个性质：一个结点的左子树的val都小于等于它，它的右子树的val都大于等于它。
    image.png
  • 概念搞清楚了，那就好好分析题目
+ 首先由题目的限制条件可以知道，**root不是一个空树**（因为它`k的限制`条件告诉我们它肯定能找到一个元素）
+ 我们要找到第K大元素，那么我们就要**先遍历二叉树**？怎样遍历这是一个问题。仔细想想：要遍历而且要找到第K大元素，那么我们首先是不是要找到一个递增或递减的顺序呢？哦，悟了悟了！我们要找这样的一个顺序，要么递增，要么递减。
+ 现在就该想想我们该用那种遍历方式呢？前序？中序？后序？想想它们的遍历顺序，再结合二叉树的性质，还有就是我们要找的是一个递增或者递减的顺序。
+ 分析之后，`我们选择了中序遍历`，这是一个递增的顺序。（还有一种方法哦！不知道给起个什么名字,暂且叫我假中序遍历，哈哈哈）
  • 直接看代码呗
  • 递归版的
1
2
3
4
5
6
7
8
9
10
11
12
ini复制代码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];
};

image.png

  • 迭代版的
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
ini复制代码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];
};

image.png

另一种方法

  • 我们的思路还是不变，还是要找一个有序的顺序，我们找的是一个递减的顺序。
  • 递归版的
1
2
3
4
5
6
7
8
9
10
11
ini复制代码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];
};

image.png

  • 迭代版的
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
ini复制代码 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];
};

image.png

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

结尾

  • 希望各位学习算法的朋友能够坚持下去，加油！
  • 若有任何问题，欢迎下方留言，小嘟看到会第一时间回复的。
  • 创作不易，觉得还不错的，欢迎支持支持！
  • 多想多做多尝试，实在不会的话，直接看代码，用代码来理解。

附件

  • 二叉树中序遍历
+ 递归版:[juejin.cn/post/702748…](https://dev.newban.cn/7027482621089153038)
+ 迭代版:[juejin.cn/post/702774…](https://dev.newban.cn/7027747932711419935)

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%