力扣272-BST前去后继,dfn序列的滑动窗口

  |  

$1 题目

题目链接

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]

$2 题解

算法1: 中序遍历

deque 实现 dfn 序上的滑动窗口

二叉查找树的中序遍历是单调递增序列。在中序遍历过程中,节点值到 target 的距离

1
abs(root -> val - target)

会是先下降后上升的过程。

在中序遍历中,始终用一个双端队列维护最近访问到的 k 个值,可以理解为树形滑动窗口。

1
deque<int> deq;

该队列只能从尾部压入,但是可以从头部或者尾部弹出。双端队列中的序列,其节点值到 target 的距离也是一个先下降后上升的。边界情况:可能没有下降的部分(target是最小值),或者没有上升的部分(target是最大值)。

这三种情况,双端队列的两端一定有一个是到 target 的距离最大的,记为 max。现在新来了一个值,如果它到 target 的距离比当前队列对应的最大值 max 还大,则后面来的值到 target 的距离只会更大,所以搜索可以提前退出了。

1
max(abs(deq.back() - target), abs(deq.front() - target)) <= abs(root -> val - target)

否则,就把队列中的最大值对应的节点弹出(队头大就弹出队头,队尾大就弹出队尾),然后把新值压入队尾。直到满足提前退出条件,或者中序遍历已完成。

1
2
3
4
5
if(abs(deq.back() - target) < abs(deq.front() - target))
deq.pop_front();
else
deq.pop_back();
deq.push_back(root -> val);

给中序遍历的递归函数加一个 bool 返回值,当子树遍历返回 true 的结果,直接返回 true,不再继续遍历。

1
bool _inOrder(TreeNode* root, double target, int k, deque<int>& deq)

给 dfs 函数加一个 bool 返回值是控制 dfs 提前退出的常用办法

时间复杂度 O(N),因为有提前退出,所以目标的 K 个数在很靠前的位置会很快。

代码(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
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: BST 上的查找 + BST 前驱后继

先二分查找离 target 最接近的节点 closest,然后在 closest 的基础上分别找 k 个前驱,k 个后继,然后合并。

在二叉查找树中找离 target 最接近的节点 closest 就是这道题的过程 270. 最接近的二叉搜索树值

给定节点 cur 找前驱(中序遍历的上一个节点)的过程:

(1) 若 cur 有左子, 则前驱节点即为 cur->left 的最右子

1
2
3
4
5
6
7
8
9
10
11
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 是不是其父节点的右子。若是,则其父点即为目标节点;否则继续沿着父亲链往上找,直到找到某个点,它是它的父节点的右子;或者没父亲节点了,则说明已经找到了最小的节点。

1
2
3
while(father[cur] && father[cur] -> right != cur)
cur = father[cur];
return father[cur];

给定节点 cur 找后继(中序遍历的下一个节点)的过程:与找前驱思路一样,把左右换一下即可。参考 510. 二叉搜索树中的中序后继 II

由于给定节点找前驱和后继需要当前节点的父节点,所以需要用一个哈希表来记录访问过的节点的父节点,二分查找的过程和查找前驱后继的过程均需要记录。根节点的父节点记为空。

1
2
unordered_map<TreeNode*, TreeNode*> father;
father[root] = nullptr;

用哈希表来保存两个节点指针之间的映射关系,是 O(1) 地找到链表或者树上待操作位置的常用办法

时间复杂度:查找目标值 closest 是O(H), 找一次前驱后继是O(H), 总共O(kH)。

树平衡时,$H = \log N$

代码(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
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);
}
}
};

Share