Using MaxHeap and DFS to solve this problem timeO(n)


  • 0
    M

    ""
    class Pair {
    int val;
    double target;
    public Pair(int a, double target) {
    this.val = a;
    this.target = target;
    }
    }
    public class Solution {
    public List<Integer> closestKValues(TreeNode root, double target, int k) {
    List<Integer> result = new ArrayList<>();
    if (root == null) return result;
    PriorityQueue<Pair> maxHeap = new PriorityQueue<> ((a,b) -> ((int)(Math.abs(b.val - b.target) - Math.abs(a.val - a.target))));
    DFS(root, target, maxHeap, k);
    copyToList(result, maxHeap);
    return result;
    }
    private void DFS(TreeNode root, double target, PriorityQueue<Pair> maxHeap, int k) {
    if (root == null) return;
    if (maxHeap.size() < k) maxHeap.offer(new Pair(root.val, target));
    else {
    Pair temp = maxHeap.peek();
    if (Math.abs(temp.val - target) > Math.abs(target - root.val)) {
    maxHeap.poll();
    maxHeap.offer(new Pair(root.val, target));
    }
    }
    DFS(root.left, target, maxHeap, k);
    DFS(root.right, target, maxHeap, k);
    }
    private void copyToList(List<Integer> result, PriorityQueue<Pair> maxHeap) {
    while (maxHeap.size() != 0) {
    result.add((int)maxHeap.poll().val);
    }
    }
    }

    ""


Log in to reply
 

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