题目链接
272. 最接近的二叉搜索树值 II
题目描述
给定一个不为空的二叉搜索树和一个目标值 target，请在该二叉搜索树中找到最接近目标值 target 的 k 个值。
注意：
1. 给定的目标值 target 是一个浮点数
2. 你可以默认 k 值永远是有效的，即 k ≤ 总结点数
3. 题目保证该二叉搜索树中只会存在一种 k 个值集合最接近目标值
样例
输入: root = [4,2,5,1,3]，目标值 = 3.714286，且 k = 2
4
/
2 5
/
1 3
输出: [4,3]
拓展
假设该二叉搜索树是平衡的，请问您是否能在小于
O
(
n
)（n 为总结点数）的时间复杂度内解决该问题呢？
算法1: 二叉树中序遍历 + 树形滑动窗口 + 提前退出
二叉查找树的中序遍历是单调递增序列。在中序遍历过程中，节点值到 target 的距离
abs(root -> val - target)
会是先下降后上升的过程。在中序遍历中，始终用一个
双端队列维护最近访问到的 k 个值
，可以理解为树形滑动窗口。
滑动窗口
是一大类算法，力扣中有很多题，主要变化是维护滑动窗口中的数据用的数据结构，常用的有哈希表，堆，单调队列。
单调队列：862. 和至少为 K 的最短子数组, 239. 滑动窗口最大值
哈希表：340. 至多包含 K 个不同字符的最长子串
堆：480. 滑动窗口中位数
deque<int> deq;
该队列只能从尾部压入，但是可以从头部或者尾部弹出。双端队列中的序列，其节点值到 target 的距离也是一个先下降后上升的。边界情况：可能没有下降的部分(target是最小值)，或者没有上升的部分(target是最大值)。
这三种情况，双端队列的两端一定有一个是到 target 的距离最大的，记为 max。现在新来了一个值，如果它到 target 的距离比当前队列对应的最大值 max 还大，则后面来的值到 target 的距离只会更大，所以搜索可以提前退出了。
max(abs(deq.back() - target), abs(deq.front() - target)) <= abs(root -> val - target)
否则，就把队列中的最大值对应的节点弹出(队头大就弹出队头，队尾大就弹出队尾)，然后把新值压入队尾。直到满足提前退出条件，或者中序遍历已完成。
if(abs(deq.back() - target) < abs(deq.front() - target))
deq.pop_front();
else
deq.pop_back();
deq.push_back(root -> val);
给中序遍历的递归函数加一个 bool 返回值，当子树遍历返回 true 的结果，直接返回 true，不再继续遍历。
bool _inOrder(TreeNode* root, double target, int k, deque<int>& deq)
给 dfs 函数加一个 bool 返回值是控制 dfs 提前退出的常用办法，例如 79. 单词搜索，60. 第k个排列，1377. T 秒后青蛙的位置
时间复杂度 O(N)，因为有提前退出，所以目标的 K 个数在很靠前的位置会很快。
代码(c++)
class Solution {
public:
vector<int> closestKValues(TreeNode* root, double target, int k) {
deque<int> deq;
_inOrder(root, target, k, deq);
vector<int> result(deq.begin(), deq.end());
return result;
}
private:
bool _inOrder(TreeNode* root, double target, int k, deque<int>& deq)
{
if(root -> left)
if(_inOrder(root -> left, target, k, deq))
return true;
if((int)deq.size() < k)
{
deq.push_back(root -> val);
}
else if(max(abs(deq.back() - target), abs(deq.front() - target)) <= abs(root -> val - target))
return true;
else
{
if(abs(deq.back() - target) < abs(deq.front() - target))
deq.pop_front();
else
deq.pop_back();
deq.push_back(root -> val);
}
if(root -> right)
if(_inOrder(root -> right, target, k, deq))
return true;
return false;
}
};
算法2: 二分查找 + 找前驱后继
先二分查找离 target 最接近的节点 closest，然后在 closest 的基础上分别找 k 个前驱，k 个后继，然后合并。
在二叉查找树中找离 target 最接近的节点 closest 就是这道题的过程 270. 最接近的二叉搜索树值
给定节点 cur 找前驱(中序遍历的上一个节点)
的过程：
(1) 若 cur 有左子, 则前驱节点即为 cur->left 的最右子
if(cur -> left)
{
father[cur -> left] = cur;
cur = cur -> left;
while(cur -> right)
{
father[cur -> right] = cur;
cur = cur -> right;
}
return cur;
}
(2) 若 cur 无左子, 则看 cur 是不是其父节点的右子。若是，则其父点即为目标节点；否则继续沿着父亲链往上找，直到找到某个点，它是它的父节点的右子；或者没父亲节点了，则说明已经找到了最小的节点。
while(father[cur] && father[cur] -> right != cur)
cur = father[cur];
return father[cur];
给定节点 cur 找后继(中序遍历的下一个节点)的过程：与找前驱思路一样，把左右换一下即可。参考 510. 二叉搜索树中的中序后继 II
由于给定节点找前驱和后继需要当前节点的父节点，所以需要用一个哈希表来记录访问过的节点的父节点，二分查找的过程和查找前驱后继的过程均需要记录。根节点的父节点记为空。
unordered_map<TreeNode*, TreeNode*> father;
father[root] = nullptr;
用哈希表来保存两个节点指针之间的映射关系，是 O(1) 地找到链表或者树上待操作位置的常用办法。
例如：138. 复制带随机指针的链表 146. LRU缓存机制
时间复杂度：查找目标值 closest 是O(H), 找一次前驱后继是O(H), 总共O(kH)。
树平衡时，H = logN
代码(c++)
class Solution_2 {
public:
vector<int> closestKValues(TreeNode* root, double target, int k) {
TreeNode *closest = root;
double min_gap = abs(root -> val - target);
unordered_map<TreeNode*, TreeNode*> father;
father[root] = nullptr;
_bisearch(root, target, closest, min_gap, father);
vector<int> result(k);
result[0] = closest -> val;
TreeNode *precursor = _get_precursor(closest, father);
TreeNode *successor = _get_successor(closest, father);
for(int i = 1; i < k; ++i)
{
if(!successor)
{
result[i] = precursor -> val;
precursor = _get_precursor(precursor, father);
continue;
}
if(!precursor)
{
result[i] = successor -> val;
successor = _get_successor(successor, father);
continue;
}
if(abs(precursor -> val - target) < abs(successor -> val - target))
{
result[i] = precursor -> val;
precursor = _get_precursor(precursor, father);
}
else
{
result[i] = successor -> val;
successor = _get_successor(successor, father);
}
}
return result;
}
private:
TreeNode* _get_precursor(TreeNode* root, unordered_map<TreeNode*, TreeNode*>& father)
{
if(root -> left)
{
father[root -> left] = root;
root = root -> left;
while(root -> right)
{
father[root -> right] = root;
root = root -> right;
}
return root;
}
while(father[root] && father[root] -> right != root)
root = father[root];
return father[root];
}
TreeNode* _get_successor(TreeNode* root, unordered_map<TreeNode*, TreeNode*>& father)
{
if(root -> right)
{
father[root -> right] = root;
root = root -> right;
while(root -> left)
{
father[root -> left] = root;
root = root -> left;
}
return root;
}
while(father[root] && father[root] -> left != root)
root = father[root];
return father[root];
}
void _bisearch(TreeNode* root, double target, TreeNode*& closest, double& min_gap,
unordered_map<TreeNode*, TreeNode*>& father)
{
if(abs(root -> val - target) < min_gap)
{
min_gap = abs(root -> val - target);
closest = root;
}
if(root -> val > target && root -> left)
{
father[root -> left] = root;
_bisearch(root -> left, target, closest, min_gap, father);
}
if(root -> val < target && root -> right)
{
father[root -> right] = root;
_bisearch(root -> right, target, closest, min_gap, father);
}
}
};