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


  • 0
    X

    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) {
                q.offer(root.val);
            } else {
                double diff1 = Math.abs(q.peek() - target);
                double diff2 = Math.abs(root.val - target);
                if (diff1 > diff2) {
                    q.poll();
                    q.offer(root.val);
                }
            }
            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>();
    		stack.push(root);
    		while (!stack.isEmpty()) {
    			TreeNode node = stack.pop();
    			pq.add(node.val);
    			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) {
    			result.add(pq.poll());
    		}
    		return result;
        }
    

Log in to reply
 

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