230. Kth Smallest Element in a BST
Given the root
of a binary search tree, and an integer k
, return the kth
smallest value (1-indexed) of all the values of the nodes in the tree.
Example 1:
Example 2:
Solution:
/**
* 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 {
public int kthSmallest(TreeNode root, int k) {
if (root == null){
return -1;
}
PriorityQueue<TreeNode> maxHeap = new PriorityQueue<TreeNode>(new Comparator<TreeNode>(){
@Override
public int compare(TreeNode t1, TreeNode t2){
if (t1.val > t2.val){
return -1;
}else if (t1.val == t2.val){
return 0;
}else{
return 1;
}
}
});
DFS(root, maxHeap, k);
return maxHeap.poll().val;
}
private void DFS(TreeNode root, PriorityQueue<TreeNode> maxHeap, int k){
if (root == null){
return;
}
if (maxHeap.size() < k){
maxHeap.offer(root);
}else if (maxHeap.peek().val > root.val){
maxHeap.poll();
maxHeap.offer(root);
}
DFS(root.left, maxHeap, k);
DFS(root.right, maxHeap, k);
}
}
//TC: O(n)
//SC: O(n)
/**
* 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 {
public int kthSmallest(TreeNode root, int k) {
PriorityQueue<Integer> pq = new PriorityQueue<Integer>(Collections.reverseOrder()); // max heap 初始化为最大堆
helper(root, k, pq);
return pq.poll();
}
private void helper(TreeNode root, int k, PriorityQueue<Integer> pq){
if (root == null){
return;
}
if (pq.size() < k){ // If size is not k yet then add any element
pq.add(root.val);
}else if (root.val < pq.peek()){
pq.poll(); // pop the top
pq.add(root.val); // add cur value to pq
}
helper(root.left, k, pq);
helper(root.right, k, pq);
return;
}
}
//Time complexity: O(n) + O(log(n)) = O(n)
//Space complexity: O(n)