Problems
LeetCode : 2096. Step-By-Step Directions From a Binary Tree Node to Another
[Lowest Common Ancestor, LCA]
LeetCode : 759. Employee Free Time
[RB-Tree]
LeetCode : 250. Count Univalue Subtrees
[DFS]
LeetCode : 2265. Count Nodes Equal to Average of Subtree
[DFS]
LeetCode : 1145. Binary Tree Coloring Game
[tree][graph]
LeetCode : 958. Check Completeness of a Binary Tree
[tree][BFS][binary tree]
LeetCode : 379. Design Phone Directory
[red-black tree][hash table][queue][linked-list]
LeetCode : 298. Binary Tree Longest Consecutive Sequence
[Tree][DFS]
LeetCode : 2415. Reverse Odd Levels of Binary Tree
[Tree][DFS]
LeetCode : 1361. Validate Binary Tree Nodes
[Tree][DFS][BFS][Graph][Binary Search][Union Find]
LeetCode : 954. Array of Doubled Pairs
[Ordered Set ( red-black tree )][Greedy][Sorting]
[Hash Table]
LeetCode : 2331. Evaluate Boolean Binary Tree
[DFS]
LeetCode : 2461. Maximum Sum of Distinct Subarrays With Length K
[ordered map][sliding window][hash table][array]
LeetCode : 1028. Recover a Tree From Preorder Traversal
[Tree][String][Stack][Depth-First-Tree][Binary Tree][hard]
LeetCode : 2491. Divide Players Into Teams of Equal Skill
[Ordered Map]
LeetCode : 2476. Closest Nodes Queries in a Binary Search Tree
[Tree]
LeetCode : 732. My Calendar III
[Ordered Tree][Line Sweep][Segment Tree][Overlap Detection][hard]
—
LeetCode 236. Lowest Common Ancestor of a Binary Tree
LeetCode 1644. Lowest Common Ancestor of a Binary Tree II
LeetCode 1650. Lowest Common Ancestor of a Binary Tree III
LeetCode 1676. Lowest Common Ancestor of a Binary Tree IV
LeetCode 235. Lowest Common Ancestor of a Binary Search Tree
LeetCode : 2096. Step-By-Step Directions From a Binary Tree Node to Another
- 尋找 Lowest Common Ancestor ( LCA )。
- LCA 跟 srcValue 的高度差就是 U 的數量。
- 接著再從 LCA 找到 destValue，即可得解。
TODO : 看看其他人怎麼解的
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
void findLCA(TreeNode *root, bool *findSrc, bool *findDest, TreeNode **lca, int startValue, int destValue, int *lcaDepth, int *srcDepth, int depth) {
if(*lca != NULL) {
return;
}
bool nowFindSrc = false;
bool nowFindDest = false;
if(root->val == startValue) {
*srcDepth = depth;
nowFindSrc = true;
}
if(root->val == destValue) {
nowFindDest = true;
}
if(root->left) {
findLCA(root->left, &nowFindSrc, &nowFindDest, lca, startValue, destValue, lcaDepth, srcDepth, depth + 1);
}
if(root->right) {
findLCA(root->right, &nowFindSrc, &nowFindDest, lca, startValue, destValue, lcaDepth, srcDepth, depth + 1);
}
/* important ! */
if(nowFindSrc && nowFindDest && *lca == NULL) {
*lcaDepth = depth;
*lca = root;
}
*findSrc |= nowFindSrc;
*findDest |= nowFindDest;
}
void findDest(TreeNode *root, string &s, int destValue, bool *found) {
if(root->val == destValue) {
*found = true;
return;
}
if(root->left) {
s.push_back('L');
findDest(root->left, s, destValue, found);
if(*found) {
return;
}
s.pop_back();
}
if(root->right) {
s.push_back('R');
findDest(root->right, s, destValue, found);
if(*found) {
return;
}
s.pop_back();
}
}
string getDirections(TreeNode* root, int startValue, int destValue) {
string s;
bool nowFindSrc = false;
bool nowFindDest = false;
TreeNode *lca = NULL;
int lcaDepth;
int destDepth;
findLCA(root, &nowFindSrc, &nowFindDest, &lca, startValue, destValue, &lcaDepth, &destDepth, 0);
int num = destDepth - lcaDepth;
for(int i = 0;i < num;i++) {
s += "U";
}
bool found = false;
findDest(lca, s, destValue, &found);
return s;
}
};LeetCode : 759. Employee Free Time
每新增一個區間時，用新區間的 start 去查找大於等於新區間 start，且離新區間 start 最近的 end ，並檢查這兩個區間有沒有交疊，若有交疊便合併在一起。最後輸出沒有被涵蓋到的區間。在合併區間時，記得要檢查合併後的區間，有沒有與其他的區間交疊。
TODO : 太慢了，想一下能不能加速，或看其他人怎麼解的
/*
// Definition for an Interval.
class Interval {
public:
int start;
int end;Interval() {}Interval(int _start, int _end) {
start = _start;
end = _end;
}
};
*/class Solution {
public:
map<int, int> e2s; // end to start
bool isOverlap(Interval &a, Interval &b) {
if(a.start < b.start) {
return a.end >= b.start;
} else {
return b.end >= a.start;
}
return false;
}
vector<Interval> employeeFreeTime(vector<vector<Interval>> schedule) {
vector<Interval> vi;
e2s[-1] = -1; // fake interval
e2s[100000001] = 100000001;
for(int i = 0;i < schedule.size();i++) {
for(int j = 0;j < schedule[i].size();j++) {
auto it = e2s.lower_bound(schedule[i][j].start);
if(-1 == it->first) {
// e2s[schedule[i][j].end] = schedule[i][j].start;
} else if(100000001 == it->first) {
// printf("100000001!\n");
e2s[schedule[i][j].end] = schedule[i][j].start;
} else {
Interval findi = {it->second, it->first};
Interval addi = {schedule[i][j].start, schedule[i][j].end};
while(isOverlap(addi, findi)) {
e2s.erase(findi.end);
addi.start = min(addi.start, findi.start);
addi.end = max(addi.end, findi.end);
it = e2s.lower_bound(addi.start);
if(100000001 == it->first) {
break;
}
findi = {it->second, it->first};
}
e2s[addi.end] = addi.start;
}
}
}
int preEnd = -1;
for(auto i = e2s.begin();i != e2s.end();i++) {
Interval nowi = {i->second, i->first};
if(-1 == nowi.end) {
continue;
} else if(-1 == preEnd) {
preEnd = nowi.end;
continue;
} else if(100000001 == nowi.start) {
break;
}
vi.push_back({preEnd, nowi.start});
preEnd = nowi.end;
}
return vi;
}
};
LeetCode : 250. Count Univalue Subtrees
class Solution {
private:
int ans = 0;
public:
bool dfs(TreeNode *root, int parentV) {
bool res = true;
if(root->left) {
res &= dfs(root->left, root->val);
}
if(root->right) {
res &= dfs(root->right, root->val);
}
if(res) {
ans++;
}
return (root->val == parentV) & res;
}
int countUnivalSubtrees(TreeNode* root) {
if(!root) {
return 0;
}
dfs(root, -1001);
return ans;
}
};LeetCode : 2265. Count Nodes Equal to Average of Subtree
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
private:
int ans = 0;
public:
// nn : num of nodes
void dfs(TreeNode *root, int *sum, int *nn) {
int localSum = 0;
int localNn = 0;
if(root->left) {
dfs(root->left, &localSum, &localNn);
}
if(root->right) {
dfs(root->right, &localSum, &localNn);
}
localNn += 1;
localSum += root->val;
if((localSum / localNn) == root->val) {
ans++;
}
*nn += localNn;
*sum += localSum;
}
int averageOfSubtree(TreeNode* root) {
int sum = 0;
int nn = 0;
dfs(root, &sum, &nn);
return ans;
}
};LeetCode : 1145. Binary Tree Coloring Game
// TODO : 實在是太慢了
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
private:
unordered_map<TreeNode *, TreeNode *> n2p;
TreeNode *px = nullptr;
TreeNode *pr = nullptr; // root
TreeNode *ans = nullptr;
public:
// 選定 y 點
// 兩點分別做 dfs or bfs，碰到彼此就停止
//
// 節點能分為只有 x 能到，以及只有 y 能到，以及兩者都能到
// 可以想想要怎麼比大小
// 因為節點數很少，可以直接遍尋 y ( 要先一次 dfs, bfs 取得所有節點資訊 )
void dfs_get_parent(TreeNode *root, TreeNode *parent, int x) {
if(root->val == x) {
px = root;
}
n2p[root] = parent;
if(root->left) {
dfs_get_parent(root->left, root, x);
}
if(root->right) {
dfs_get_parent(root->right, root, x);
}
}
void dfs_get_stat_x(TreeNode *root, int y, unordered_map<TreeNode *, int> &stat) {
if(root->val == y) {
return;
}
// the node is visited
if(stat[root] & 1) {
return;
}
stat[root] += 1;
if(root->left) {
dfs_get_stat_x(root->left, y, stat);
}
if(root->right) {
dfs_get_stat_x(root->right, y, stat);
}
if(n2p[root]) {
dfs_get_stat_x(n2p[root], y, stat);
}
}
void dfs_get_stat_y(TreeNode *root, int x, unordered_map<TreeNode *, int> &stat) {
if(root->val == x) {
return;
}
// the node is visited
if(stat[root] & 2) {
return;
}
stat[root] += 2;
if(root->left) {
dfs_get_stat_y(root->left, x, stat);
}
if(root->right) {
dfs_get_stat_y(root->right, x, stat);
}
if(n2p[root]) {
dfs_get_stat_y(n2p[root], x, stat);
}
}
void dfs_count_stat(TreeNode *root, unordered_map<TreeNode *, int> &stat, vector<int> &countStat) {
countStat[stat[root]]++;
if(root->left) {
dfs_count_stat(root->left, stat, countStat);
}
if(root->right) {
dfs_count_stat(root->right, stat, countStat);
}
}
bool choose_a_point(TreeNode *root, int n, int x) {
// stat :
// 1 --> only x
// 2 --> only y
// 3 --> both x & y
unordered_map<TreeNode *, int> stat;
vector<int> countStat = vector<int>(4, 0);
dfs_get_stat_x(px, root->val, stat);
dfs_get_stat_y(root, x, stat);
dfs_count_stat(pr, stat, countStat);int t = 0;
if(countStat[3] % 2 == 0) {
t = countStat[3] / 2;
} else {
t = countStat[3] / 2 + 1;
}
int sumx = countStat[1] + t;
int sumy = countStat[2] + (countStat[3] - t);
if(sumy > sumx) {
return true;
}
if(root->left) {
if(choose_a_point(root->left, n, x)) {
return true;
}
}
if(root->right) {
if(choose_a_point(root->right, n, x)) {
return true;
}
}
return false;
}
bool btreeGameWinningMove(TreeNode* root, int n, int x) {
pr = root;
dfs_get_parent(root, nullptr, x);
return choose_a_point(root, n, x);
}
};
LeetCode : 958. Check Completeness of a Binary Tree
// TODO : 時間空間效能太差
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*//*
1. 只有最後一排能缺，都沒缺的話，就直接 return true
2. 最後一排有缺的話，倒數第二排有缺之後，就不能再缺了
3. 所有的節點，只能缺右子節點，不能缺左子節點*/
class Solution {
public:
bool isCompleteTree(TreeNode* root) {
// heights
vector<int> hs;
// level order nodes
vector<vector<TreeNode *>> nodes;
queue<TreeNode *> q;
q.push(root);
int nowLevel = 0;
int nowNum = 1;
int nextNum = 0;
nodes.push_back(vector<TreeNode *>(0));
hs.push_back(1);
while(!q.empty()) {
TreeNode *nown = q.front();
nodes[nowLevel].push_back(nown);
q.pop();
if(nown->left) {
q.push(nown->left);
nextNum++;
}
if(nown->right) {
q.push(nown->right);
nextNum++;
}
nowNum--;
if(0 == nowNum) {
nodes.push_back(vector<TreeNode *>(0));
hs.push_back(nextNum);
nowNum = nextNum;
nextNum = 0;
nowLevel++;
}
// 假如有缺，只能缺右邊
if(((!!nown->left) != (!!nown->right)) &&
nown->right) {
return false;
}
}
if(0 == nodes.back().size()) {
nodes.pop_back();
}
if(0 == hs.back()) {
hs.pop_back();
}
// 假如數量都對的話，直接 return true
bool f = true;
for(int i = 0;i < hs.size();i++) {
if(hs[i] != pow(2, i)) {
// 假如不是在最後一個缺的話，就 return false
if(i != hs.size() - 1) {
return false;
} else {
f = false;
}
}
}
if(f) {
return true;
}
// 假如數量不對，倒數第二排有漏掉的那個節點以後，
// 都不能有子節點
if(nodes.size() >= 2) {
vector<TreeNode *> tmp = nodes[nodes.size() - 2];
bool check = false;
for(int i = 0;i < tmp.size();i++) {
if(!check) {
if((!tmp[i]->left) || (!tmp[i]->right)) {
check = true;
}
} else {
if((tmp[i]->left) || (tmp[i]->right)) {
return false;
}
}
}
} return true;
}
};
LeetCode : 379. Design Phone Directory
// TODO : 效能太差了，用 doubly-linked-list 應該會更快?
// 題目有點難懂
class PhoneDirectory {
public:
// empty map
map<int, bool> em;
// used map
map<int, bool> um;
PhoneDirectory(int maxNumbers) {
for(int i = 0;i < maxNumbers;i++) {
em[i] = true;
}
}
int get() {
if(em.empty()) {
return -1;
}
int ret = em.begin()->first;
em.erase(ret);
um[ret] = true;
return ret;
}
bool check(int number) {
return em.find(number) != em.end();
}
void release(int number) {
if(um.find(number) != um.end()) {
um.erase(number);
em[number] = true;
}
}
};/**
* Your PhoneDirectory object will be instantiated and called as such:
* PhoneDirectory* obj = new PhoneDirectory(maxNumbers);
* int param_1 = obj->get();
* bool param_2 = obj->check(number);
* obj->release(number);
*/
LeetCode : 298. Binary Tree Longest Consecutive Sequence
// medium
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int maxVal = 0;
void dfs(TreeNode *root, int nowv) {
maxVal = max(maxVal, nowv);
if(root->left) {
if(root->left->val ==
root->val + 1) {
dfs(root->left, nowv + 1);
} else {
dfs(root->left, 1);
}
}
if(root->right) {
if(root->right->val ==
root->val + 1) {
dfs(root->right, nowv + 1);
} else {
dfs(root->right, 1);
}
}
}
int longestConsecutive(TreeNode* root) {
if(root == NULL) {
return 0;
}
dfs(root, 1);
return maxVal;
}
};LeetCode : 2415. Reverse Odd Levels of Binary Tree
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
void dfs(TreeNode *root, int level, vector<vector<TreeNode*>> &rec) {
if(level % 2 == 1) {
int index = (level - 1) / 2;
if(rec.size() < index + 1) {
rec.push_back({});
}
rec[index].push_back(root);
}
if(root->left) {
dfs(root->left, level + 1, rec);
dfs(root->right, level + 1, rec);
}
}
TreeNode* reverseOddLevels(TreeNode* root) {
vector<vector<TreeNode*>> rec;
dfs(root, 0, rec);
for(int i = 0;i < rec.size();i++) {
int left = 0;
int right = rec[i].size() - 1;
while(left < right) {
int tmp = rec[i][left]->val;
rec[i][left]->val = rec[i][right]->val;
rec[i][right]->val = tmp;
left++;
right--;
}
}
return root;
}
};LeetCode : 1361. Validate Binary Tree Nodes
// TODO : 程式碼太醜了
class Solution {
public:
bool dfs(int nown, vector<bool> &visited, vector<int>& leftChild, vector<int>& rightChild) {
visited[nown] = true;
if(leftChild[nown] != -1) {
if(visited[leftChild[nown]]) {
return false;
}
if(!dfs(leftChild[nown], visited, leftChild, rightChild)) {
return false;
}
}
if(rightChild[nown] != -1) {
if(visited[rightChild[nown]]) {
return false;
}
if(!dfs(rightChild[nown], visited, leftChild, rightChild)) {
return false;
}
}
return true;
}
bool validateBinaryTreeNodes(int n, vector<int>& leftChild, vector<int>& rightChild) {
vector<bool> visited = vector<bool>(n, false);
vector<int> inDegree = vector<int>(n, 0);
for(int i = 0;i < n;i++) {
if(leftChild[i] >= 0) {
inDegree[leftChild[i]]++;
}
if(rightChild[i] >= 0) {
inDegree[rightChild[i]]++;
}
}
bool first = false;
for(int i = 0;i < n;i++) {
if(inDegree[i] == 0) {
if(first) {
return false;
}
first = true;
if(!dfs(i, visited, leftChild, rightChild)) {
return false;
}
}
}
for(int i = 0;i < n;i++) {
if(!visited[i]) {
return false;
}
}
return first;
}
};LeetCode : 954. Array of Doubled Pairs
// 從數字最小的開始處理
// 比較特別的是，當遇到負數的時候，要找 minVal / 2
// 遇到正數，要找 minVal * 2
class Solution {
public:
bool canReorderDoubled(vector<int>& arr) {
map<int, int> m;
for(int i = 0;i < arr.size();i++) {
m[arr[i]]++;
}
while(!m.empty()) {
int minVal = m.begin()->first;
m[minVal]--;
if(m[minVal] == 0) {
m.erase(minVal);
}
int goal;
if(minVal < 0) {
if(minVal % 2 != 0) {
return false;
}
goal = minVal / 2;
} else {
goal = minVal * 2;
}
if(m.find(goal) == m.end()) {
return false;
}
m[goal]--;
if(m[goal] == 0) {
m.erase(goal);
}
}
return true;
}
};LeetCode : 2331. Evaluate Boolean Binary Tree
// DFS
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
void dfs(TreeNode *root) {
if(root->val == 0 ||
root->val == 1) {
return;
}
if(root->left &&
(root->left->val == 2) ||
root->left->val == 3) {
dfs(root->left);
}
if(root->right &&
(root->right->val == 2) ||
root->right->val == 3) {
dfs(root->right);
}
if(root->val == 2) {
root->val = root->left->val | root->right->val;
} else if (root->val == 3) {
root->val = root->left->val & root->right->val;
}
}
bool evaluateTree(TreeNode* root) {
dfs(root);
return root->val == 1;
}
};LeetCode : 2461. Maximum Sum of Distinct Subarrays With Length K
// TODO : 效能太差
#define LL long long
class Solution {
public:
long long maximumSubarraySum(vector<int>& nums, int k) {
map<LL, int> m;
map<LL, int> times_map;
LL sum = 0;
LL ans = 0;
for (int i = 0;i < k;i++) {
sum += nums[i];
m[nums[i]]++;
}
for(auto it = m.begin();it != m.end();it++) {
times_map[it->second]++;
}
if(times_map.rbegin()->first < 2) {
ans = max(ans, sum);
}
for(int i = k;i < nums.size();i++) {
int time = m[nums[i - k]];
m[nums[i - k]]--;
times_map[time]--;
sum -= nums[i - k];
if(m[nums[i - k]] != 0) {
times_map[m[nums[i - k]]]++;
}
if(times_map[time] == 0) {
times_map.erase(time);
}
m[nums[i]]++;
times_map[m[nums[i]]]++;
sum += nums[i];
if(times_map.rbegin()->first < 2) {
ans = max(ans, sum);
}
}
return ans;
}
};LeetCode : 1028. Recover a Tree From Preorder Traversal
// preOrder --> 中左右
// TODO : 效能太差
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* recoverFromPreorder(string traversal) {
vector<vector<int>> tra;
vector<TreeNode *> sta;
int nowd = 0;
string tmps;
for(int i = 0;i < traversal.size();i++) {
if(traversal[i] >= '0' &&
traversal[i] <= '9') {
tmps.push_back(traversal[i]);
} else if (traversal[i] == '-') {
if(tmps.size() > 0) {
tra.push_back({atoi(tmps.c_str()), nowd});
tmps.clear();
nowd = 0;
}
nowd++;
}
}
if (tmps.size() > 0) {
tra.push_back({atoi(tmps.c_str()), nowd});
}
TreeNode *head = new TreeNode(tra[0][0]);
sta.push_back(head);
for(int i = 1;i < tra.size();i++) {
// stack.size() - 1 == 當前 TreeNode 的深度
while(sta.size() > tra[i][1]) {
sta.pop_back();
}
TreeNode *nowh = sta.back();
TreeNode *newn = new TreeNode(tra[i][0]);
sta.push_back(newn);
if(!nowh->left) {
nowh->left = newn;
} else {
nowh->right = newn;
}
}
return head;
}
};
LeetCode : 2491. Divide Players Into Teams of Equal Skill
#define LL long long
class Solution {
public:
long long dividePlayers(vector<int>& skill) {
map<LL, LL> m;
LL sum = 0;
LL len = skill.size() / 2;
LL single = 0;
LL ans = 0;
for(int i = 0;i < skill.size();i++) {
sum += skill[i];
m[skill[i]]++;
}
if(sum % len != 0) {
return -1;
}
single = sum / len;
while(!m.empty()) {
int now = m.begin()->first;
int goal = single - now;
if (now > single ||
goal > single) {
return -1;
} else if (m.find(goal) == m.end()) {
return -1;
} else if (now == goal &&
m[goal] == 1) {
return -1;
}
m[now]--;
if(m[now] == 0) {
m.erase(now);
}
m[goal]--;
if(m[goal] == 0) {
m.erase(goal);
}
ans += goal * now;
}
return ans;
}
};LeetCode : 2476. Closest Nodes Queries in a Binary Search Tree
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
void dfs(TreeNode *root, vector<int> &s) {
if(root->left) {
dfs(root->left, s);
}
s.push_back(root->val);
if(root->right) {
dfs(root->right, s);
}
}
vector<vector<int>> closestNodes(TreeNode* root, vector<int>& queries) {
// 給予的 binary search tree 可能是退化的版本
// 最好還是要自己整理成 sorted array
vector<vector<int>> ans;
vector<int> s;
dfs(root, s);
for(int i = 0;i < queries.size();i++) {
int maxVal = INT_MAX;
int minVal = INT_MIN;
int left = 0;
int right = s.size() - 1;
while(left <= right) {
int mid = (left + right) / 2;
if (s[mid] > queries[i]) {
maxVal = min(maxVal, s[mid]);
right = mid - 1;
} else if(s[mid] == queries[i]) {
maxVal = s[mid];
minVal = s[mid];
break;
} else if(s[mid] < queries[i]) {
minVal = max(minVal, s[mid]);
left = mid + 1;
}
}
ans.push_back({
minVal == INT_MIN ? -1 : minVal,
maxVal == INT_MAX ? -1 : maxVal});
}
return ans;
}
};LeetCode : 732. My Calendar III
// 要注意的是，這題是要求從以前到現在，k 的最大值
// 並非只是當前 k 的值
// TODO : 試著用 segment tree 來解這一題
class MyCalendarThree {
public:
map<int, vector<int>> m;
int maxk = INT_MIN;
MyCalendarThree() {
}
int book(int startTime, int endTime) {
if(m.find(startTime) == m.end()) {
m[startTime] = vector<int>(2, 0);
}
m[startTime][0]++;
if(m.find(endTime) == m.end()) {
m[endTime] = vector<int>(2, 0);
}
m[endTime][1]++;
int nowk = 0;
for(auto it = m.begin();it != m.end();it++) {
if(it->first > endTime) {
break;
}
nowk += it->second[0];
nowk -= it->second[1];
maxk = max(maxk, nowk);
}
return maxk;
}
};
/**
* Your MyCalendarThree object will be instantiated and called as such:
* MyCalendarThree* obj = new MyCalendarThree();
* int param_1 = obj->book(startTime,endTime);
*/
