【LeetCode】二叉查找树 binary search tree（共14题）

链接：https://leetcode.com/tag/binary-search-tree/

【220】Contains Duplicate III (2019年4月20日) （好题）

Given an array of integers, find out whether there are two distinct indices i and j in the array such that the absolute difference between nums[i] and nums[j] is at most t and the absolute difference between i and j is at most k.

Example 1:
Input: nums = [1,2,3,1], k = 3, t = 0
Output: true
Example 2:
Input: nums = [1,0,1,1], k = 1, t = 2
Output: true
Example 3:
Input: nums = [1,5,9,1,5,9], k = 2, t = 3
Output: false

题解：

解法1. brute force。 O(NK)

解法2. set + lower_bound(), sliding window, time complexity: O(NlogK), space O(K)

解法3. bucket：unordered_map<int, int> : key bucket idx, value nums[i], time complexity: O(N), space: O(K)

 1 class Solution {
 2 public:
 3     bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
 4         if (k <= 0 || t < 0) {return false;}
 5         set<int> st;
 6         for (int i = 0; i < nums.size(); ++i) {
 7             int num = nums[i];
 8             auto iter = st.lower_bound(num);
 9             if (iter != st.end()) {
10                 int greater = *iter;
11                 if ((long)greater - num <= t) {return true;}
12             }
13             if (iter != st.begin()) {
14                 --iter;
15                 int less = *iter;
16                 if ((long)num - less <= t) {return true;}
17             }
18             if (st.size() == k) {
19                 st.erase(nums[i-k]);
20             }
21             st.insert(num);
22         }
23         return false;
24     }
25 };

solution2

 1 class Solution {
 2 public:
 3     bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
 4         if (nums.empty() || k <= 0 || t < 0) {return false;}
 5         long bucketSize = (long)t + 1;
 6         int minn = nums.front();
 7         for (auto& num : nums) {
 8             minn = min(num, minn);
 9         }
10         unordered_map<long, int> bucket; //key: bucketIdx, value: nums[i]
11         for (int i = 0; i < nums.size(); ++i) {
12             long bucketIdx = ((long)nums[i] - minn) / bucketSize;
13             if (bucket.count(bucketIdx)) {return true;}
14             int left = bucketIdx - 1, right = bucketIdx + 1;
15             if (bucket.count(left) && (long)nums[i] - bucket[left] <= t) {return true;}
16             if (bucket.count(right) && (long)bucket[right] - nums[i] <= t) {return true;}
17             if (i >= k) {
18                 long removeKey = ((long)nums[i-k] - minn) / bucketSize;
19                 bucket.erase(removeKey);
20             }
21             bucket[bucketIdx] = nums[i];
22         }
23         return false;
24     }
25 };

solution3

【315】Count of Smaller Numbers After Self

【327】Count of Range Sum

【352】Data Stream as Disjoint Intervals

【493】Reverse Pairs

【530】Minimum Absolute Difference in BST （2019年3月10日）（Easy）

返回一棵 BST的两个结点的最小绝对值的距离之差。

Given a binary search tree with non-negative values, find the minimum absolute difference between values of any two nodes.

题解：根据 BST 的性质，我们只需要用一个变量记录中序遍历的前一个结点prev即可。

 1 /**
 2  * Definition for a binary tree node.
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 class Solution {
11 public:
12     int getMinimumDifference(TreeNode* root) {
13         if (!root) {return 0;}
14         inorder(root);
15         return res;
16     }
17     int res = INT_MAX;
18     TreeNode* prev = nullptr;
19     void inorder(TreeNode* root) {
20         if (!root) {return;}
21         inorder(root->left);
22         if (prev) {
23             res = min(res, root->val - prev->val);
24         }
25         prev = root;
26         inorder(root->right);
27         return;
28     }
29 };

View Code

【683】K Empty Slots

【699】Falling Squares

【715】Range Module

【731】My Calendar II （2019年3月21日）

题意是每次给定一个 event [start, end) ，如果插入这个 event 之后，当前有个时刻的同时进行的 event 的数量大于等于 3，那么就不插入这个 event，返回这个 event 能不能被插入。

此题只要找出所有与[start,end)重合的区间，再检查这些区间是否有互相的重合。是的话，说明必然有triple booking。

【732】My Calendar III （2019年3月21日）

题意是每次插入一个 event，返回插入这个event之后，对于任意一个时刻，同时在进行的 event 有多少个。

https://leetcode.com/problems/my-calendar-iii/description/

sweep line 的思想，用一个 multiset，记录 event 和 event 类型，如果是 start，event就表示成{start, 1}, 如果是 end，event 就表示成 {end, -1}，然后每次插入之后，去遍历 multiset，如果碰到 1，就 +1，如果碰到 -1 ，就 -1。

【776】Split BST

【783】Minimum Distance Between BST Nodes （2019年3月10日）（Easy）

返回一棵 BST的两个结点的最小的距离之差。

Given a Binary Search Tree (BST) with the root node root, return the minimum difference between the values of any two different nodes in the tree.

题解：同上面 530 题，一样的解法。

【938】Range Sum of BST