O(k + logn) java solution using two queue


  • 0
    F

    When tree is balanced, this solution is O(k + log(n))

    public class Solution {
        public List<Integer> closestKValues(TreeNode root, double target, int k) {
            List<Integer> res = new ArrayList<>();
            Deque<Integer> sq = new ArrayDeque<>();
            Deque<Integer> bq = new ArrayDeque<>();
            traverse(root, target, k, sq, bq);
            addResult(res, sq, bq, target, k);
            return res;
        }
        
        public void traverse(TreeNode root, double target, int k, Deque<Integer> sq, Deque<Integer> bq) {
            if (root == null) {return;}
            if (root.val > target) {
                traverse(root.left, target, k, sq, bq);
                if (bq.size() < k) {bq.addFirst(root.val);}
                if (bq.size() < k) {traverse(root.right, target, k, sq, bq);}
            } else if (root.val < target) {
                traverse(root.right, target, k, sq, bq);
                if (sq.size() < k) {sq.addFirst(root.val);}
                if (sq.size() < k) {traverse(root.left, target, k, sq, bq);}
            } else {
                sq.addFirst(root.val);
                if (sq.size() < k) {traverse(root.left, target, k, sq, bq);}
                if (bq.size() < k) {traverse(root.right, target, k, sq, bq);}
            }
        }
        
        public void addResult(List<Integer> res, Deque<Integer> sq, Deque<Integer> bq, double target, int k) {
            while (!sq.isEmpty() && !bq.isEmpty() && res.size() < k) {
                double small = Math.abs(sq.getLast() - target);
                double big = Math.abs(bq.getLast() - target);
                res.add(small > big ? bq.removeLast() : sq.removeLast());
            }
            while (!sq.isEmpty() && res.size() < k) {
                res.add(sq.removeLast());
            }
            while (!bq.isEmpty() && res.size() < k) {
                res.add(bq.removeLast());
            }
        }
    }
    
    

Log in to reply
 

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