原题链接在这里：https://leetcode.com/problems/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:
Follow up:
Assume that the BST is balanced, could you solve it in less than O(n) runtime (where n = total nodes)?
与Closest Binary Search Tree Value相似。
维护一个maxHeap. 若是maxHeap size小于k就加现在的diff. 等到size 等于 k 时，若是现在的diff比peek的小，就要替换。若是现在diff 比 peek大，就继续扫描，但根据BST性质，可以只扫描一边。
Time Complexity: O(n). Space: O(k). 若果不考虑recursion stack.
AC Java:
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<Integer> closestKValues(TreeNode root, double target, int k) { 12 List<Integer> res = new ArrayList<Integer>(); 13 if(root == null){ 14 return res; 15 } 16 17 PriorityQueue<Double> maxHeap = new PriorityQueue<Double>(Collections.reverseOrder()); 18 HashSet<Integer> hs = new HashSet<Integer>(); 19 20 helper(root, target, k, maxHeap, hs); 21 22 return new ArrayList<Integer>(hs); 23 } 24 25 private void helper(TreeNode root, double target, int k, PriorityQueue<Double> maxHeap, HashSet<Integer> hs){ 26 if(root == null){ 27 return; 28 } 29 30 double diff = Math.abs(root.val - target); 31 if(maxHeap.size() < k){ 32 maxHeap.add(diff); 33 hs.add(root.val); 34 }else if(diff < maxHeap.peek()){ 35 double peek = maxHeap.poll(); 36 maxHeap.add(diff); 37 hs.remove((int)(target + peek)); 38 hs.remove((int)(target - peek)); 39 hs.add(root.val); 40 }else{ 41 if(target > root.val){ 42 helper(root.right, target, k, maxHeap, hs); 43 }else{ 44 helper(root.left, target, k, maxHeap, hs); 45 } 46 return; 47 } 48 helper(root.left, target, k, maxHeap, hs); 49 helper(root.right, target, k, maxHeap, hs); 50 } 51 }
找出一个最小值，从BST中删掉这个key.
Time Complexity: O(k*logn).
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<Integer> closestKValues(TreeNode root, double target, int k) { 12 List<Integer> res = new ArrayList<Integer>(); 13 if(root == null){ 14 return res; 15 } 16 17 for(int i = 0; i<k ;i++){ 18 int closest = closestValue(root, target); 19 res.add(closest); 20 root = deleteNode(root, closest); 21 } 22 23 return res; 24 } 25 26 private int closestValue(TreeNode root, double target){ 27 if(root == null){ 28 return Integer.MAX_VALUE; 29 } 30 int closest = root.val; 31 double minDiff = Double.MAX_VALUE; 32 while(root != null){ 33 if(Math.abs(root.val - target) < minDiff){ 34 minDiff = Math.abs(root.val - target); 35 closest = root.val; 36 } 37 38 if(target > root.val){ 39 root = root.right; 40 }else if(target < root.val){ 41 root = root.left; 42 }else{ 43 return root.val; 44 } 45 } 46 return closest; 47 } 48 49 private TreeNode deleteNode(TreeNode root, int key){ 50 if(root == null){ 51 return root; 52 } 53 54 if(root.val > key){ 55 root.left = deleteNode(root.left, key); 56 }else if(root.val < key){ 57 root.right = deleteNode(root.right, key); 58 }else{ 59 if(root.left == null){ 60 return root.right; 61 }else if(root.right == null){ 62 return root.left; 63 } 64 65 int suc = findSuc(root.right); 66 root.val = suc; 67 deleteNode(root.right, suc); 68 } 69 return root; 70 } 71 72 private int findSuc(TreeNode root){ 73 int suc = root.val; 74 while(root.left != null){ 75 root = root.left; 76 suc = root.val; 77 } 78 return suc; 79 } 80 }
LeetCode Closest Binary Search Tree Value II
原文：http://www.cnblogs.com/Dylan-Java-NYC/p/5204366.html