【Java实现】剑指Offer54——二叉搜索树的第K大节点（利用BST的性质遍历）思路分享

83 阅读 0 评论 55 点赞

我是靠谱客的博主整齐红牛，这篇文章主要介绍【Java实现】剑指Offer54——二叉搜索树的第K大节点（利用BST的性质遍历）思路分享，现在分享给大家，希望可以做个参考。

【Java实现】剑指Offer54——二叉搜索树的第K大节点（利用BST的性质遍历）：思路分享

图片来自LeetCode
关于二叉搜索树的一些学习笔记在这里哦：

接下来几期内容会更新《剑指Offer》中所有“树”标签的习题及思路，传送门在此：

解题思路：
从题目看到二叉搜索树，就要联想到BST的性质：

中序遍历是递增的

我们都知道二叉树的中序遍历：

先遍历左子树，然后根节点，最后右子树

既然BST这样遍历能得到递增序列，那如何得到递减序列呢？

先遍历右子树、然后根节点、最后左子树，即可得到递减序列

到这里，大体的思路已经确定，就是采用递归的方式遍历BST，而要获得第k大的数，只需要加一个计数器即可。

思路如下：

每遍历到一个数，都要判断当前计数器的状态
假设计数器初始值为k，当计数器归零时，即得到结果
此时递归即可终止，返回值即可

代码如下：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    //需要定义全局变量，计数器和结果
    private int count,res;

    public int kthLargest(TreeNode root, int k) {
        //让计数器递减
        this.count=k;
        dfs(root);
        return res;
    }
    public void dfs(TreeNode root) {
        //递归终止条件
        if(root==null) return;
        //先遍历右子树
        dfs(root.right);

        //回来遍历当前节点，通过count判断
        if(count==0) return;
        if(--count==0) res=root.val;

        //最后递归左子树
        dfs(root.left);
    }
}