Java very easy to understand solution. traverse once only


  • 0
    J

    traverse once.

        public List<Integer> closestKValues(TreeNode root, double target, int k) {
            List<Integer> result = new ArrayList<>();
            if (root == null) return result;
            Stack<Integer> lessEqual = new Stack<>();
            Queue<Integer> more  = new ArrayDeque<>();
            inorder(root, target, lessEqual, more);
            for (int i = 0; i < k; i++) {
                double diff1 = !lessEqual.isEmpty() ? Math.abs(target - lessEqual.peek()) : Double.MAX_VALUE;
                double diff2 = !more.isEmpty() ? Math.abs(target - more.peek()) : Double.MAX_VALUE;
                if (diff1 < diff2) result.add(lessEqual.pop());
                else result.add(more.poll());
            }
            return result;
        }
        
        private void inorder(TreeNode root, double target, Stack<Integer> lessEqual, Queue<Integer> more) {
            if (root == null) return;
            if (root.left != null) inorder(root.left, target, lessEqual, more);
            if (root.val <= target) lessEqual.push(root.val);
            else more.offer(root.val);
            if (root.right != null) inorder(root.right, target, lessEqual, more);
        }
    

Log in to reply
 

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