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

Example

Given root ={1}, target =0.000000, k =1, return[1].

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */

public class Solution {
    /**
     * @param root: the given BST
     * @param target: the given target
     * @param k: the given k
     * @return: k values in the BST that are closest to the target
     */
    public List<Integer> closestKValues(TreeNode root, double target, int k) {
        // write your code here
        List<Integer> ans = new ArrayList<>();
        if (root == null) {
            return ans;
        }
        List<Integer> list = new ArrayList<>();
        inorderTraverse(root, list);
        //
        ans = findKclosest(list, target, k);

        //
        return ans;
    }
    public void inorderTraverse(TreeNode root, List<Integer> list) {
        if (root == null) {
            return;
        }
        inorderTraverse(root.left, list);
        list.add(root.val);
        inorderTraverse(root.right, list);
    }
    public List<Integer> findKclosest (List<Integer> list, double target, int k) {
        // int[] arr = list.toArray();
        int[] arr = list.stream().mapToInt(i->i).toArray();
        if (arr.length <= k) {
            return list;
        }
        int start = 0;
        int end = arr.length - 1;
        List<Integer> ans = new ArrayList<>();
        while (start + 1 < end) {
            int mid = (end - start) / 2 + start;
            if (arr[mid] <= target) {
                start = mid;
            }else if (arr[mid] > target){
                end = mid;
            }
        }


















        int index = 0;

        while (index < k && start >= 0 && end < arr.length ){
            if(Math.abs(arr[start] - target ) <= Math.abs(arr[end] - target) ) {
                ans.add(arr[start]);
                start--;
                index++;

            }else{
                ans.add(arr[end]);
                end++;
                index++;
            }

        }
        while (index < k && start >= 0 ) {
                ans.add(arr[start]);
                start--;
                index++;
        }
        while (index < k && end < arr.length ) {
                ans.add(arr[end]);
                end++;
                index++;
        }

        return ans;
    }

}