272. Closest Binary Search Tree Value II

      /*
       * 272. Closest Binary Search Tree Value II
       * 2016-6-25 by Mingyang
       * 一开始这个题目我想用priority queue来做，就是把所有的stack里面的全部加进来
       * 然后一个一个的找
       */
      public List<Integer> closestKValues1(TreeNode root, double target, int k) {
            Stack<TreeNode> stack = new Stack<TreeNode>();
            LinkedList<Integer> ret = new LinkedList<Integer>();
            TreeNode curr = root;
            while (curr != null || !stack.isEmpty()) {
                if (curr != null) {
                    stack.push(curr);
                    curr = curr.left;
                } else {
                    curr = stack.pop();
                    if(ret.size() < k) {
                        ret.addLast(curr.val);
                    } else {
                        if(Math.abs(ret.getFirst()-target) > Math.abs(curr.val-target)) {
                            ret.removeFirst();
                            ret.addLast(curr.val);
                        } else break;
                    }
                    curr = curr.right;
                }
            }
            return ret;
        }
      //当然priority queue也是可以的！看大神的代码：
      public List<Integer> closestKValues2(TreeNode root, double target, int k) {  
          PriorityQueue<Double> maxHeap = new PriorityQueue<Double>(k, new Comparator<Double>() {   
                @Override  
                public int compare(Double x, Double y) {  
                    return (int)(y-x);  
                }  
            });  
            Set<Integer> set = new HashSet<Integer>();  
            rec(root, target, k, maxHeap, set);                
            return new ArrayList<Integer>(set);  
        }        
        private void rec(TreeNode root, double target, int k, PriorityQueue<Double> maxHeap, Set<Integer> set) {  
            if(root==null) return;  
            double diff = Math.abs(root.val-target);  
            if(maxHeap.size()<k) {  
                maxHeap.offer(diff);  
                set.add(root.val);  
            } else if( diff < maxHeap.peek() ) {  
                double x = maxHeap.poll();  
                if(! set.remove((int)(target+x))) set.remove((int)(target-x));  
                maxHeap.offer(diff);  
                set.add(root.val);  
            } else {  
                if(root.val > target) rec(root.left, target, k, maxHeap,set);  
                else rec(root.right, target, k, maxHeap, set);  
                return;  
            }  
            rec(root.left, target, k, maxHeap, set);  
            rec(root.right, target, k, maxHeap, set);  
        }