Leetcode 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.

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

Solution 1: travel through the BST to build stack left stack and right stack. Each time find the min peek of the two, pop and rebuild one of the stack.

 public class Solution {  
   public List<Integer> closestKValues(TreeNode root, double target, int k) {  
     Deque<TreeNode> left=new LinkedList<>();  
     Deque<TreeNode> right=new LinkedList<>();  
     TreeNode x=root;  
     while (x!=null) {  
       if (x.val>target) {  
         right.push(x);  
         x=x.left;  
       }  
       else {  
         left.push(x);  
         x=x.right;  
       }  
     }  
     List<Integer> res=new ArrayList<>();  
     while (res.size()<k) {  
       if (left.isEmpty()) nextRight(right,res);  
       else if (right.isEmpty()) nextLeft(left,res);  
       else if (target-left.peek().val<right.peek().val-target) nextLeft(left,res);  
       else nextRight(right,res);  
     }  
     return res;  
   }  
   private void nextRight(Deque<TreeNode> right, List<Integer> res) {  
     TreeNode x=right.pop();  
     res.add(x.val);  
     x=x.right;  
     while (x!=null) {  
       right.push(x);  
       x=x.left;  
     }  
   }  
   private void nextLeft(Deque<TreeNode> left, List<Integer> res) {  
     TreeNode x=left.pop();  
     res.add(x.val);  
     x=x.left;  
     while (x!=null) {  
       left.push(x);  
       x=x.right;  
     }  
   }  
 }