Closest Binary Search Tree Value II

Java

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
     */
    private void findTarget(Stack<TreeNode> stack,TreeNode root,double target){
        while (root!=null){
            stack.push(root);
            if (target<root.val){
                root=root.left;
            }
            else {
                root=root.right;
            }
        }
    } 
    
    private void getNext(Stack<TreeNode> stack){
        TreeNode node=stack.peek();
        if (node.right!=null){
            node=node.right;
            while (node!=null){
                stack.push(node);
                node=node.left;
            }
        }
        else {
            while (!stack.isEmpty()){
                node=stack.pop();
                if (!stack.isEmpty() && stack.peek().right!=node){
                    break;
                }
            }
        }
    }
    
    private void getPrev(Stack<TreeNode> stack){
        TreeNode node=stack.peek();
        if (node.left!=null){
            node=node.left;
            while (node!=null){
                stack.push(node);
                node=node.right;
            }
        }
        else {
            while (!stack.isEmpty()){
                node=stack.pop();
                if (!stack.isEmpty() && stack.peek().left!=node){
                    break;
                }
            }
        }
    }
     
    public List<Integer> closestKValues(TreeNode root, double target, int k) {
        // write your code here
        Stack<TreeNode> nextStack=new Stack<>();
        Stack<TreeNode> prevStack=new Stack<>();
        findTarget(nextStack,root,target);
        prevStack.addAll(nextStack);
        getPrev(prevStack);
        
        List<Integer> answer=new ArrayList<>();
        for (int i=0;i<k;i++){
            if (prevStack.isEmpty()){
                answer.add(nextStack.peek().val);
                getNext(nextStack);
            }
            else if (nextStack.isEmpty()){
                answer.add(prevStack.peek().val);
                getPrev(prevStack);
            }
            else if (target-prevStack.peek().val<nextStack.peek().val-target){
                answer.add(prevStack.peek().val);
                getPrev(prevStack);  
            }
            else {
                answer.add(nextStack.peek().val);
                getNext(nextStack);  
            }
        }
        return answer;
    }
}