这道题惊吓到我了，从没想到LinkedList可以这样用。以前做的题都是围绕着操作LinkedList本身来用，比如反转，找交点，这才发现LinkedList作为数据结构实际的用处。它很特别，因为有getFirst()和removeFirst()这两个特别的method. ArrayList没有这些。
这道题本身并不难，实际上考到了in order traversal的写法，也考到了BST被in order traversal出来的会是non descending order这个特点。我一开始是全部把traverse过的节点再放到heap里面取离target最近的k个点。然而并不需要那样麻烦，完全可以在traverse的过程中就一边找到最近的k个点。 我们始终控制LinkedList的size在k. 当size等于k的时候，还需要加入节点时我们就检查该节点和first element in the list 哪个离target更近，取近的留下。关于为什么要getFirst()取跟最开始放进去的元素比较，我是认为因为前面那些元素因为res.size() < k, 所以会无脑放进去，但很有可能他们离target是很远的，所以我们要从first开始比较。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> closestKValues(TreeNode root, double target, int k) {
LinkedList<Integer> res = new LinkedList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode curt = root;
while (curt != null){
stack.push(curt);
curt = curt.left;
}
while (!stack.isEmpty()){
curt = stack.pop();
if (res.size() == k){
if (Math.abs(curt.val - target) >= Math.abs(res.getFirst() - target)){
break;
} else {
res.removeFirst();
}
}
res.add(curt.val);
if (curt.right != null){
curt = curt.right;
while (curt != null){
stack.push(curt);
curt = curt.left;
}
}
}
return res;
}
}
