Java Simple PriorityQueue Solution


  • 1
    8

    Just insert treenode into queue sorted by the abs(node.val - target) and take the first k ones.

    public List<Integer> closestKValues(TreeNode root, final double t, int k) {
        List<Integer>ret = new ArrayList<Integer>();
        PriorityQueue<TreeNode> queue = new PriorityQueue<TreeNode>(new Comparator<TreeNode>(){
           public int compare(TreeNode n1, TreeNode n2) {
               return Math.abs(n1.val - t) < Math.abs(n2.val - t) ? -1 : 1;
           }
        });
        findClosest(root, queue);
        while(k-- > 0) ret.add(queue.poll().val);
        return ret;
    }
    
    public void findClosest(TreeNode root, PriorityQueue<TreeNode> queue) {
        if(root == null) return;
        findClosest(root.left, queue);
        queue.add(root);
        findClosest(root.right, queue);
    }

  • 0
    I

    This is NLogN right? Since it takes O(N) to go through the tree and LogN to add to the queue? WOuld this be acceptable solution to give in interview?


Log in to reply
 

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