[272. Closest Binary Search Tree Value II] #leetcode

272_0903.java

// O(n) O(n)
class Solution {
    public List<Integer> closestKValues(TreeNode root, double target, int k) {
        List<Integer> res = new ArrayList<Integer>();
        
        Deque<Integer> pre = new LinkedList<Integer>();
        Deque<Integer> suc = new LinkedList<Integer>();
        
        inorder(root, target, false, pre);
        inorder(root, target, true, suc);
        
        while (k-- > 0) {
            if (pre.isEmpty()) res.add(suc.pop());
            else if (suc.isEmpty()) res.add(pre.pop());
            else if (Math.abs(suc.peek() - target) < Math.abs(pre.peek() - target)) res.add(suc.pop());
            else res.add(pre.pop());
        }
        
        return res;
        
    }
    
    private void inorder(TreeNode node, double target, boolean reverse, Deque<Integer> stack) {
        if (node == null) return;
        
        inorder(reverse ? node.right : node.left, target, reverse, stack);
        if ((reverse && node.val <= target) || (!reverse && node.val > target)) return;
        stack.push(node.val);
        inorder(reverse ? node.left : node.right, target, reverse, stack);
    }
}