Given a non-empty binary search tree and a target value, findkvalues 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 thanO(n) runtime (wheren= total nodes)?

/**
 * 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> ans = new ArrayList<>();

        Stack<Integer> s1 = new Stack<>();
        Stack<Integer> s2 = new Stack<>();

        inorder(root, target, s1, false);
        inorder(root, target, s2, true);

        while (k-- > 0){
            if (s1.isEmpty()){
                ans.add(s2.pop());
            }
            else if (s2.isEmpty()){
                ans.add(s1.pop());
            }
            else if (Math.abs(s1.peek() - target) < Math.abs(s2.peek() - target)){
                ans.add(s1.pop());
            }
            else{
                ans.add(s2.pop());
            }
        }

        return ans;
    }

    private void inorder(TreeNode root, double target, Stack<Integer> s, boolean reverse){
        if (root == null) return;

        inorder(reverse ? root.right : root.left, target, s, reverse);
        if (!reverse && root.val > target || reverse && root.val <= target) return;
        s.push(root.val);
        inorder(reverse ? root.left : root.right, target, s, reverse);
    }
}