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)?

Hint:

1. Consider implement these two helper functions:
   1. getPredecessor(N), which returns the next smaller node to N.
   2. getSuccessor(N), which returns the next larger node to N.
2. Try to assume that each node has a parent pointer, it makes the problem much easier.
3. Without parent pointer we just need to keep track of the path from the root to the current node using a stack.
4. You would need two stacks to track the path in finding predecessor and successor node separately.

 用一个栈一个队列，用recursion写inorder Traversal, Time: O(N+K), Space: O(N)

1 /** 2  * Definition for a binary tree node. 3  * public class TreeNode { 4  *     int val; 5  *     TreeNode left; 6  *     TreeNode right; 7  *     TreeNode(int x) { val = x; } 8  * } 9  */10 public class Solution {11     public List
          
            closestKValues(TreeNode root, double target, int k) {12         List
           
             res = new ArrayList
            
             ();13         LinkedList
             
               stack = new LinkedList
              
               ();14         LinkedList
               
                 queue = new LinkedList
                
                 ();15 inorder(root, target, stack, queue);16 for (int i=0; i
                 
                   stack, LinkedList
                  
                    queue) {36 if (root == null) return;37 inorder(root.left, target, stack, queue);38 if (root.val < target) {39 stack.push(root.val);40 }41 else {42 queue.offer(root.val);43 }44 inorder(root.right, target, stack, queue);45 }46 }
                  
                 
                
               
              
             
            
           
          

 

Better Idea: 只用一个大小为K的队列的方法：Time O(N), Space O(K)

前K个数直接加入队列，之后每来一个新的数（较大的数），如果该数和目标的差，相比于队头的数离目标的差来说，更小，则将队头拿出来，将新数加入队列。如果该数的差更大，则直接退出并返回这个队列，因为后面的数更大，差值也只会更大。

1 /** 2  * Definition for a binary tree node. 3  * public class TreeNode { 4  *     int val; 5  *     TreeNode left; 6  *     TreeNode right; 7  *     TreeNode(int x) { val = x; } 8  * } 9  */10 public class Solution {11     public List
          
            closestKValues(TreeNode root, double target, int k) {12         //List
           
             res = new ArrayList
            
             ();13         LinkedList
             
               stack = new LinkedList
              
               ();14         LinkedList
               
                 queue = new LinkedList
                
                 ();15 16 while (!stack.isEmpty() || root!=null) {17 if (root != null) {18 stack.push(root);19 root = root.left;20 }21 else {22 root = stack.pop();23 if (queue.size() < k) {24 queue.offer(root.val);25 }26 else {27 if (Math.abs(root.val-target) < Math.abs(queue.peek()-target)) {28 queue.poll();29 queue.offer(root.val);30 }31 else break;32 }33 root = root.right;34 }35 }36 37 return (List
                 
                  )queue;38 }39 40 }