Closest Binary Search Tree Value II(Hard)
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)?
解题思路：中序遍历结果是将树中元素从小到大排列，逆式的中序遍历即先遍历右子树再访问根节点最后遍历左子树会得到树中元素从大到小排列的结果，因此可通过中序遍历获取最接近target节点的perdecessors，通过逆中序遍历获取最接近target节点的successors,然后merge perdecessors 和 successors 获取最接近target节点的 k个节点值。
注意到在中序遍历时遇到比target大的节点即停止，因为由BST的性质可知后面的元素均会比target 大，即所有target的predecessors均已找到，同理逆中序遍历时遇到不大于 target的节点即可停止递归
public List<Integer> closestKValues(TreeNode root, double target, int k) {
List<Integer> result = new ArrayList<Integer>();
LinkedList<Integer> stackPre = new LinkedList<Integer>();
LinkedList<Integer> stackSucc = new LinkedList<Integer>();
inorder(root, target, false, stackPre);
inorder(root, target, true, stackSucc);
while (k-- > 0) {
if (stackPre.isEmpty()) {
result.add(stackSucc.pop());
} else if (stackSucc.isEmpty()) {
result.add(stackPre.pop());
} else if (Math.abs(stackPre.peek() - target) < Math.abs(stackSucc.peek() - target)) {
result.add(stackPre.pop());
} else {
result.add(stackSucc.pop());
}
}
return result;
}
public void inorder(TreeNode root, double target, boolean reverse, LinkedList<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);
}