[Leetcode 230][Medium] 二叉搜索树中第 K 小的元素-大根堆/优先队列/DFS深度优先搜索

本文主要是介绍[Leetcode 230][Medium] 二叉搜索树中第 K 小的元素-大根堆/优先队列/DFS深度优先搜索，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

一、题目描述

二、整体思路

三、代码

---

一、题目描述

题目地址

二、整体思路

        大根堆/优先队列

        看到第K小的元素（Top K）问题，第一时间想到快速排序/大根堆/优先队列。比较简单的思路是把所有结点加入到优先队列，然后重复出队列操作使得队列中元素数量为k,此时队首元素即为第K小的元素。优先队列的数据结构是大根堆,在遇见比堆顶小的元素时直接替换堆顶并维护大根堆，当大根堆元素数量为K时此时堆顶的意义为全体元素中最小的K个数中最大的数，也就是第K小的数。

快排代码在此题不太适合，和二叉搜索树的特性没什么联系了。

        DFS深度优先搜索

        二叉搜索树的特性是每个节点比其左子树所有节点要大,比其右子树所有节点要小。那么我们可以用DFS优先把左子树遍历完再遍历右子树，回溯的同时令K-1。当K==1时遍历到的结点即为第K小的结点。(二叉搜索树的前序遍历即按升序顺序把所有节点遍历一遍，DFS与前序遍历有相同之处)

        要注意的是需要在类内设立两个成员变量来暂存当前K值和当前第K的元素值。K不可以作为参数传入dfs。

三、代码

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {//大根堆/优先队列PriorityQueue<Integer> pq=new PriorityQueue<>((x,y)->(y-x));public int kthSmallest(TreeNode root, int k) {preorder(root);while(pq.size()!=k){pq.poll();}return pq.peek();}public void preorder(TreeNode node){if(node==null){return;}pq.add(node.val);preorder(node.left);preorder(node.right);return;}
}

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {//dfsint tar;int k;public int kthSmallest(TreeNode root, int k) {this.k=k;dfs(root);return tar;}public void dfs(TreeNode node){if(node==null || k<=0){return;}dfs(node.left);if(k==1){tar=node.val;k--;return;}k--;dfs(node.right);}
}

这篇关于[Leetcode 230][Medium] 二叉搜索树中第 K 小的元素-大根堆/优先队列/DFS深度优先搜索的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---