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

 

1 /** 2  * Definition for a binary tree node. 3  * public class TreeNode { 4  *     public int val; 5  *     public TreeNode left; 6  *     public TreeNode right; 7  *     public TreeNode(int x) { val = x; } 8  * } 9  */10 public class Solution {11     public IList
      
        ClosestKValues(TreeNode root, double target, int k) {12         var result = new List
       
        ();13         14         Stack
        
          s1 = new Stack
         
          (), s2 = new Stack
          
           ();15         Inorder(root, target, true, s1);16         Inorder(root, target, false, s2);17         18         for (int i = 0; i < k; i++)19         {20             if (s1.Count == 0)21             {22                 result.Add(s2.Pop());23             }24             else if (s2.Count == 0)25             {26                 result.Add(s1.Pop());27             }28             else29             {30                 double d1 = Math.Abs((double)s1.Peek() - target);31                 double d2 = Math.Abs((double)s2.Peek() - target);32                 33                 if (d1 < d2)34                 {35                     result.Add(s1.Pop());36                 }37                 else38                 {39                     result.Add(s2.Pop());40                 }41             }42         }43         44         return result;45     }46     47     48     private void Inorder(TreeNode node, double target, bool reverse, Stack
           
             stack)49 {50 if (node == null) return;51 52 Inorder(reverse ? node.right : node.left, target, reverse, stack);53 54 if (reverse ? (double)node.val <= target : (double)node.val > target)55 {56 return;57 }58 59 stack.Push(node.val);60 61 Inorder(reverse ? node.left : node.right, target, reverse, stack);62 }63 }