Java O(logN) DFS solution using PriorityQueue


  • -2
    G
    public class Solution {
    
    public List<Integer> closestKValues(TreeNode root, double target, int k) {
        final double t = target;
        List<Integer> rst = new ArrayList<Integer>(k);
        rst.addAll(dfs(root, target, k, new PriorityQueue<Integer>(k, 
                new Comparator<Integer>(){ // offset descending order
                    @Override
                    public int compare(Integer o1, Integer o2) {
                        if (o1.intValue() == o2.intValue()) return 0;
                        return (Math.abs(o1 - t) < Math.abs(o2 - t)) ? 1 : -1; 
                    }
                })));        
        return rst;
    }
    
    private PriorityQueue<Integer> dfs(TreeNode root, double target, int k, PriorityQueue<Integer> queue) {
        int v = root.val;
        if (queue.size() < k) { 
        	queue.offer(v); 
        } else if ((Math.abs(v - target) < Math.abs(queue.peek() - target))) { 
        	queue.poll(); //head is the furthest element in current K nearest elements
        	queue.offer(v);
        } 
        
        if (root.left != null) { queue = dfs(root.left, target, k, queue); }
        if (root.right != null) { queue = dfs(root.right, target, k, queue); }
        
        return queue;
    }
    }

  • 0
    S

    Is it O(n) ? The task was to do it faster


Log in to reply
 

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