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); } }