Java solution with priorityQueue


  • 0
    C
    public class Solution {
        public class Pair {
            public int val;
            public double dis;
            public Pair(int val, double dis) {
                this.val = val;
                this.dis = dis;
            }
            
            @Override
            public String toString() {
                return val + ", " + dis;
            }
        }
        
        
        PriorityQueue<Pair> result;
        public List<Integer> closestKValues(TreeNode root, double target, int k) {
            result = new PriorityQueue<Pair>(k, new DistanceCompare());
            findClosest(root, target, k);
            List<Integer> list = new ArrayList<>();
            for(Pair entry : result) {
                list.add(entry.val);
            }
            return list;
        }
        
        public class DistanceCompare implements Comparator<Pair> {
            @Override
            public int compare(Pair a, Pair b) {
               if(b.dis > a.dis) return 1;
               else if(b.dis < a.dis) return -1;
               else return 0;
            }
        }
        
        private void findClosest(TreeNode node, double target, int k) {
            if(node == null) return;
            double dif = node.val - target;
            double curDistance = Math.abs(dif);
            Pair entry = new Pair(node.val, curDistance);
            result.offer(entry);
            // System.out.println(result);
            if(result.size() > k) result.poll();
            findClosest(node.left, target, k);
            findClosest(node.right, target, k);
        }
    }
    

Log in to reply
 

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