O(n) one pass solution with one queue (Recursion)

  • 0

    The idea is very straightforward. I use a queue and inorder traverse the whole tree so that we can meet element in sorted order.

    • If queue.size() < k. Just put element into queue.

    • If queue.size() >= k. We compare root.val with q.peek() and dequeue when |target - q.peek()| > |target - q.peek()|. We can make sure all the elements are closer to target since we meet elements in sorted order.

      public class Solution {

        public List<Integer> closestKValues(TreeNode root, double target, int k) {
            Queue<Integer> q = new LinkedList<Integer>();
            inorderTraverse(root, q, target, k);
            return (List<Integer>)q;
        public void inorderTraverse(TreeNode root, Queue<Integer> q, double target, int k) {
            if (root == null) return;
            inorderTraverse(root.left, q, target, k);
            if (q.size() < k) {
            } else {
                double diff1 = Math.abs(q.peek() - target);
                double diff2 = Math.abs(root.val - target);
                if (diff1 > diff2) {
            inorderTraverse(root.right, q, target, k);


  • 0

    @xctom I came up with something similar; too bad it's O(NlgN) in the worst case -_- :

        public List<Integer> closestKValues(TreeNode root, double target, int k) {
            if (root == null) return new ArrayList<>();
    		PriorityQueue<Integer> pq = new PriorityQueue<>(k,
    				(a, b) -> Double.compare(Math.abs(a - target), Math.abs(b - target)));
    		Stack<TreeNode> stack = new Stack<TreeNode>();
    		while (!stack.isEmpty()) {
    			TreeNode node = stack.pop();
    			if (node.right != null) stack.push(node.right);
    			if (node.left != null) stack.push(node.left);
    		List<Integer> result = new ArrayList<>();
    		while (!pq.isEmpty() && k-- > 0) {
    		return result;

Log in to reply

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