Problem:
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)?
Analysis:
This problem is not hard. But the description of the problem is really quite misleading. It strongly hints you to use the characteristics of balance tree. I fail to achieve that. But there is also a very innovative and efficient way to solve this problem. Ask: Where are closest nodes of a give number ?
The predecessors and successors of a given number are the best candidates for you to choice, based on how many closest nodes you want.
And we already know through a inorder traversal we shoud easily get the tree in sorted form. It's really easy for us to find the closestKValues in the sorted form.
1 2 3 5 6 [target: 7] 8 10 23 25 But for this problem, we could solve it in more elegant way. Use the idea we have used in merging k sorted list.
Predecessors list: 6 5 3 2 1
Successors: 8 10 23 25 Basic knowledge enhancement
Through ordinary preorder traversal (scan left subtree first), we could get the binary search tree in the ascending order.
1 2 3 5 6 8 10 23 25
Through reverse preorder traversal (scan right subtree first), we could get the binary search tree in the descending order.
25 23 10 8 6 5 3 2 1 Step 1: get the predecessors list : 6 5 3 2 1 (descending order), through a stack.
------------------------------------------------------------------------
preOrderTraversal(is_reverse ? root.left, target, stack, is_reverse);
...
stack.push(root.val)
preOrderTraversal(is_reverse ? root.right, target, stack, is_reverse);
------------------------------------------------------------------------ Step 2: get the successors list : 8 10 23 25 (ascending order), through a stack.
------------------------------------------------------------------------
preOrderTraversal(is_reverse ? root.right, target, stack, is_reverse);
...
stack.push(root.val)
preOrderTraversal(is_reverse ? root.left, target, stack, is_reverse);
------------------------------------------------------------------------ A skill in getting "6 5 3 2 1" rather than "25 23 10 8 6 5 3 2 1".
if ((!is_reverse && root.val > target))
return;
//Great during the traversal process, we stop when we reach a node larger than target. A skill in getting "8 10 23 25" rahter than "25 23 10 8 6 5 3 2 1"
if (is_reverse && root.val <= target)
return;
Note: we use the same termination skill at here. Another skill to be careful (note when there is a stack was used up)
if (pre.isEmpty()) {
ret.add(suc.pop());
} else if (suc.isEmpty()) {
ret.add(pre.pop());
}
You must detect and handle above cases.
Solution:
public class Solution {
public List<Integer> closestKValues(TreeNode root, double target, int k) {
List<Integer> ret = new ArrayList<Integer> ();
Stack<Integer> pre = new Stack<Integer> ();
Stack<Integer> suc = new Stack<Integer> ();
preOrderTraversal(root, target, pre, false);
preOrderTraversal(root, target, suc, true);
int count = 0;
while (count < k) {
if (pre.isEmpty()) {
ret.add(suc.pop());
} else if (suc.isEmpty()) {
ret.add(pre.pop());
} else if (Math.abs(target - pre.peek()) < Math.abs(target - suc.peek())) {
ret.add(pre.pop());
} else {
ret.add(suc.pop());
}
count++;
}
return ret;
}
private void preOrderTraversal(TreeNode root, double target, Stack<Integer> stack, boolean is_reverse) {
if (root == null)
return;
preOrderTraversal(is_reverse ? root.right : root.left, target, stack, is_reverse);
if ((is_reverse && root.val <= target) || (!is_reverse && root.val > target))
return;
stack.push(root.val);
preOrderTraversal(is_reverse ? root.left : root.right, target, stack, is_reverse);
}
}