BiruLyu
8/10/2017 - 9:52 PM

## 272. Closest Binary Search Tree Value II(#).java

``````/**
* 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<Integer> closestKValues(TreeNode root, double target, int k) {
List<Integer> list=new ArrayList<Integer>();
inOrder(root, list);

if(list.size()<=k){
return list;
}

int pos=binarySearch(list, 0, list.size()-1, target);

List<Integer> res=new ArrayList<Integer>();
getKvals(res, list, pos, target,k);

return res;

}

public void getKvals(List<Integer> res, List<Integer> list, int pos, double target, int k){
int r=pos, l=pos-1;
while(res.size()<k && l>=0 && r<list.size()){
double left_dif=target-(double)list.get(l);
double right_dif=(double)list.get(r)-target;
if(left_dif==right_dif){
l--;
r++;
}else if(left_dif<right_dif){
l--;
}else {
r++;
}
}

while(res.size()<k && l>=0){
l--;
}

while(res.size()<k && r<list.size()){
r++;
}

return;
}

public void inOrder(TreeNode p, List<Integer> list){
if(p==null) return;
inOrder(p.left, list);
inOrder(p.right, list);
}

public int binarySearch(List<Integer> list, int i, int j, double target){
while(i<=j){
int mid=i+(j-i)/2;
double mid_val=(double) list.get(mid);
if(mid_val<target){
i=mid+1;
}else if(mid_val>target){
j=mid-1;
}else{
return mid;
}
}
return i;
}

}``````
``````/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution {

private static class CircularQueue
{
private final int[] arr;
private int size;
private int tail;

public CircularQueue(int capacity) {
arr = new int[capacity];
size = 0;
tail = 0;
}
public boolean isEmpty()
{
return size == 0;
}

{
if (size == 0) {
return -1;
}
return arr[(tail - size + arr.length) % arr.length];
}

{
arr[tail] = val;
tail = (tail + 1) % arr.length;

if (size < arr.length) {
size++;
}
}
}

public List<Integer> closestKValues(TreeNode root, double target, int k) {
CircularQueue queue = new CircularQueue(k);
closestN(root, target, k, queue);
List<Integer> result = new ArrayList<>(queue.arr.length);
for (int i : queue.arr) {
}
return result;
}

private void closestN(TreeNode root, double target, int k, CircularQueue queue)
{
if (root == null) {
return;
}

closestN(root.left, target, k, queue);

int val = root.val;
if (queue.isEmpty()) {
}
else if(queue.size < k || Math.abs(queue.getHead() - target) >= Math.abs(val - target)) {
}
else {
return;
}
closestN(root.right, target, k, queue);
}
}``````
``````public class Solution {
public List<Integer> closestKValues(TreeNode root, double target, int k) {
find(root, target, k, q);
return q;
}

void find(TreeNode cur, double target, int k, LinkedList<Integer> q){
if(cur == null) return;
else{
find(cur.left, target, k, q);
if(q.isEmpty() || q.size() < k) {
find(cur.right, target, k, q);
}
else{
if(Math.abs(target-q.getFirst()) > Math.abs(target-cur.val)){
q.removeFirst();
find(cur.right, target, k, q);
}
}
}
}
}``````
``````/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution {
private void inOrder(TreeNode root, double target, boolean reverse, Stack<Integer> stack) {
if (root == null) return;
inOrder(reverse ? root.right : root.left, target, reverse, stack);
if ((reverse && root.val <=target) || (!reverse && root.val > target)) return;
stack.push(root.val);
inOrder(reverse ? root.left : root.right, target, reverse, stack);
}
public List<Integer> closestKValues(TreeNode root, double target, int k) {
Stack<Integer> floor = new Stack<>();
Stack<Integer> greater = new Stack<>();

inOrder(root, target, false, floor);
inOrder(root, target, true, greater);

List<Integer> res = new ArrayList<>();
while (k-- > 0) {
if (floor.isEmpty()) {