# AC Java Solution with PriorityQueue, the O(log n) Time Complexity?

• public List<Integer> closestKValues(TreeNode root, double target, int k) {
List<Integer> res = new ArrayList<Integer>();
Queue<Double> q = new PriorityQueue<>(new Comparator<Double>(){
@Override
public int compare(Double arg0, Double arg1)
{
if (arg1 < arg0)
{
return -1;
}
if ( arg1  > arg0 )
{
return 1;
}
return 0;
}
});
HashMap<Double,ArrayList<Integer>> hm = new  HashMap<Double,ArrayList<Integer>>();
dfs(q, root, target, k,hm);
for(ArrayList<Integer> list:hm.values()){
res.addAll(list);
}
return res;
}
public void dfs(Queue<Double> q, TreeNode root, double target, int k, HashMap<Double,ArrayList<Integer>> hm){
if(root==null) return;
q.offer(Math.abs(root.val-target));
if(!hm.containsKey(Math.abs(root.val-target))){
ArrayList<Integer> tmp = new ArrayList<Integer>();
tmp.add(root.val);
hm.put(Math.abs(root.val-target),tmp);
}
else{
hm.get(Math.abs(root.val-target)).add(root.val);
}
if(q.size()>k){
hm.get(q.peek()).remove(0);
if(hm.get(q.peek())==null) hm.remove(q.peek());
q.poll();
}
dfs(q,root.left,target,k,hm);
dfs(q,root.right,target,k,hm);
}

• Similar idea here, but I used an inner class instead.
I am just afraid, by using the priorityQueue, we did not use the property of BST at all.

private class MyNode{
int val;
//TreeNode node;
private MyNode(int val){
this.val = val;
// this.node = node;
}
}

public List<Integer> closestKValues(TreeNode root, double target, int k) {
PriorityQueue<MyNode> pq = new PriorityQueue<MyNode>(new Comparator<MyNode>(){
public int compare(MyNode node1, MyNode node2){
if(Math.abs(target - node1.val) < Math.abs(target - node2.val)){
return -1;
}else if(Math.abs(target - node1.val) == Math.abs(target - node2.val)){
return 0;
}else{
return 1;
}
}
});

Stack<TreeNode> stack = new Stack<TreeNode>();
//TreeNode curr = root;
stack.push(root);

while(!stack.isEmpty()){
TreeNode curr = stack.pop();
pq.offer(new MyNode(curr.val));

if(curr.left != null) stack.push(curr.left);
if(curr.right != null) stack.push(curr.right);
}

List<Integer> result = new ArrayList<Integer>();

for(int i = 0; i < k; i++){
result.add(pq.poll().val);
}

return result;
}

• this is not o(logn) time. this is o(n) time.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.