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

Analysis:

Use inorder traverse, put all predecessors into a stack, for every successor, put all pres that has smaller gap than that successor into resList and then put this successor into resList.

Solution:

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode(int x) { val = x; } * } */public class Solution {    public List
     
       closestKValues(TreeNode root, double target, int k) {        Stack
      
        pres = new Stack
       
        ();        LinkedList
        
          resList = new LinkedList
         
          ();        closestKValuesRecur(root,target,k,pres,resList);        // If not enough in resList, put more pres into resList. This is because successor is too little.        while (resList.size()
          
            pres, LinkedList
           
             resList){ if (curNode == null) return; if (resList.size()==k) return; // inorder traverse. closestKValuesRecur(curNode.left,target,k,pres,resList); // check curNode if (curNode.val >= target){ while (resList.size()