0272. Closest Binary Search Tree Value II

https://leetcode.com/problems/closest-binary-search-tree-value-ii

Description

Given the root of a binary search tree, a target value, and an integer k, return the k values in the BST that are closest to the target. You may return the answer in any order.

You are guaranteed to have only one unique set of k values in the BST that are closest to the target.

Example 1:

**Input:** root = [4,2,5,1,3], target = 3.714286, k = 2
**Output:** [4,3]

Example 2:

**Input:** root = [1], target = 0.000000, k = 1
**Output:** [1]

Constraints:

• The number of nodes in the tree is n.

• 1 <= k <= n <= 104.

• 0 <= Node.val <= 109

• -109 <= target <= 109

Follow up: Assume that the BST is balanced. Could you solve it in less than O(n) runtime (where n = total nodes)?

ac: iterative, 1 list + 1 stack

O(n) time key idea is in-order traversal of BST is incremental, make use of it.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> closestKValues(TreeNode root, double target, int k) {
        List<Integer> res = new ArrayList<Integer>();
        // edge cases
        if (root == null || k <= 0) return res;

        // get in-order list
        List<Integer> inorder = new ArrayList<Integer>();
        int closestIndex = 0;
        Stack<TreeNode> stack = new Stack<>();
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            if (inorder.size() != 0 && Math.abs(target - root.val) < Math.abs(target - inorder.get(inorder.size() - 1))) closestIndex = inorder.size();
            inorder.add(root.val);
            root = root.right;
        }

        // compare left and right, add to result list
        res.add(inorder.get(closestIndex));
        int l = closestIndex - 1, r = closestIndex + 1;
        while (res.size() < k) {
            if (l < 0) {
                res.add(inorder.get(r));
                r++;
            } else if (r >= inorder.size()) {
                res.add(inorder.get(l));
                l--;
            } else if (Math.abs(target - inorder.get(l)) < Math.abs(target - inorder.get(r))) {
                res.add(inorder.get(l));
                l--;
            } else {
                res.add(inorder.get(r));
                r++;
            }
        }

        return res;
    }
}

/*
get in-order list
find closest index
compare left and right, add to result list

*/

ac2: recursive

maintain a k size window

class Solution {
    public List<Integer> closestKValues(TreeNode root, double target, int k) {
        LinkedList<Integer> res = new LinkedList<Integer>();
        // edge cases
        if (root == null || k <= 0) return res;
        traverse(root, target, k, res);
        return res;
    }
    private void traverse(TreeNode root, double target, int k, LinkedList<Integer> res) {
        // exit
        if (root == null) return;

        // root.left
        traverse(root.left, target, k, res);
        // root
        if (res.size() == k) {
            int h = res.getFirst();
            if (Math.abs(target - h) > Math.abs(target - root.val)) {
                res.removeFirst();
                res.add(root.val);
            } else {
                return;  // result found, terminate early
            }
        } else {
            res.add(root.val);
        }
        // root.right
        traverse(root.right, target, k, res);
    }
}