二叉搜索树的第k大节点(Java)

80 阅读 0 评论 53 点赞

我是靠谱客的博主动听花瓣，这篇文章主要介绍二叉搜索树的第k大节点(Java)，现在分享给大家，希望可以做个参考。

在这里插入图片描述
思路：
如果了解二叉搜索树中序遍历应该知道中序遍历的结果是升序的顺序，由此我们可以使用中序遍历遍历这棵二叉搜索树，把结果放到一个数据结构中，然后再取出倒数第K个数即可
代码：

class Solution {
	public static Stack<Integer> s = new Stack<>();
	
	public int kthLargest(TreeNode root, int k) {
        zhongxu(root);
        while(k != 0){
            k--;
            if(k == 0){
                return s.peek();
            }
            s.pop();
        }
        return 666;
    }
    
    public static void zhongxu(TreeNode root){
        if(root.left != null){
            zhongxu(root.left);
        }
        s.push(root.val);
        if(root.right != null){
            zhongxu(root.right);
        }
    }
}