Share the joy
This one is from leetcode. Given a non-empty binary search tree and a target value, find k values in the BST that are closest to the target.
This is a very interesting problem. The best solution is that we maintain a k size window. We traverse tree in-orderly. Let diffHead = abs(head – target), diffTail = abs(tail – target) and diff = max(diffHead, diffTail). So when k closest elements are in queue, we should have the minimum diff.
Suppose a below binary tree. When target = 7, k = 3, the process is like:
In this way, we know when nodes are [5, 7, 8], it gets the minimum diff.
check my code on github: link