算法leetcode

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

字数统计: 1.7k字   |   阅读时长: 7分
, ,

$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