This is Yizhe's Blog: 272. Closest Binary Search Tree Value II

Given a non-empty binary search tree and a target value, find k values in the BST that are closest to the target.

Note:

Given target value is a floating point.
You may assume k is always valid, that is: k ≤ total nodes.
You are guaranteed to have only one unique set of k values in the BST that are closest to the target.

Example:

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

    4
   / \
  2   5
 / \
1   3

Output: [4,3]

Follow up:

Assume that the BST is balanced, could you solve it in less than O(n) runtime (where n = total nodes)?

My answer: get sorted array from BST, and then find the smallest element bigger than or equal to target, and then find closet k element starting from that element.

Other solutions are put at the end.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> closestKValues(TreeNode root, double target, int k) {
        List<Integer> values = new ArrayList<Integer>();
        inorder(root, values);
        Integer[] vs = values.toArray(new Integer[0]);
        int l = 0;
        int r = vs.length - 1;
        int ceil = (int) Math.ceil(target);
        int floor = (int) Math.floor(target);
        
        // find the last element bigger than or equal to ceil,
        // and l stores the index of it
        while(l < r ) {
            int m = (l + r) / 2;
            if (vs[m] > ceil) {
                r = m;
            } else {
                l = m + 1;
            }
        }
        l --;
        r = l + 1;
        List<Integer> result = new ArrayList<Integer>();
        while (k > 0) {
            if (l == -1) {
                result.add(vs[r]);
                r++;
                k--;
                continue;
            }
            if (r == vs.length) {
                result.add(vs[l]);
                l --;
                k--;
                continue;
            }
            if (Math.abs(target - (double) vs[l]) < Math.abs(target - (double) vs[r])) {
                result.add(vs[l]);
                l --;
            } else {
                result.add(vs[r]);
                r ++;
            }
            k --;
        }
        return result;
        
    }
    
    private void inorder(TreeNode node, List<Integer> values) {
        if (node == null) {
            return;
        }
        inorder(node.left, values);
        values.add(node.val);
        inorder(node.right, values);
    }
}

Leetcode's solution: all the answers are based on array containing distance to the target.

There are three ways to solve the problem:

Approach 1. Sort, $\mathcal{O}(N \log N)$ time. The idea is to convert BST into an array, sort it by the distance to the target, and return the k closest elements.
Approach 2. Facebook-friendly, heap, $\mathcal{O}(N \log k)$ time. We could use the heap of capacity k, sorted by the distance to the target. It's not an optimal but very straightforward solution - traverse the tree, push the elements into the heap, and then return this heap. Facebook interviewer would insist on implementing this solution because the interviews are a bit shorter than Google ones, and it's important to get problem solved end-to-end.
Approach 3. Google-friendly, quickselect, $\mathcal{O}(N)$ time. Here you could find a very detailed explanation of quickselect algorithm. In this article, we're going to provide a relatively brief implementation. Google guys usually prefer the best-time solutions, well-structured clean skeleton, even if you have no time to implement everything in time end-to-end

This is Yizhe's Blog

Labels

Friday, January 29, 2021

272. Closest Binary Search Tree Value II

No comments:

Post a Comment