Сложность: medium
Вам даны два списка закрытых интервалов, firstList и secondList, где firstList[i] = [starti, endi] и secondList[j] = [startj, endj]. Каждый список интервалов является попарно непересекающимся и отсортированным.
Верните пересечение этих двух списков интервалов.
Закрытый интервал [a, b] (где a <= b) обозначает множество действительных чисел x с a <= x <= b.
Пересечение двух закрытых интервалов - это множество действительных чисел, которые либо пусты, либо представлены как закрытый интервал. Например, пересечение [1, 3] и [2, 4] равно [2, 3].
Пример:
Input: root = [3,9,20,null,null,15,7]
Output: [[9],[3,15],[20],[7]]
👨💻 Алгоритм:
1⃣Инициализация указателей:
Создать словарь для хранения узлов по их координатам (col, row).
Создать очередь для обхода в ширину (BFS), содержащую начальную пару (root, (0, 0)).
2⃣Поиск пересечений:
Выполнить BFS обход дерева. Для каждого узла сохранить его значение в словаре по ключу (col, row).
Добавить левый потомок в очередь с координатами (row + 1, col - 1).
Добавить правый потомок в очередь с координатами (row + 1, col + 1).
3⃣Возврат результата:
Отсортировать ключи словаря по col и затем по row.
Для каждого столбца, упорядочить узлы по row и значениям, и добавить их в результирующий список.
😎 Решение:
class Solution {
public:
vector<vector<int>> verticalTraversal(TreeNode* root) {
map<int, vector<pair<int, int>>> colTable;
queue<pair<TreeNode*, pair<int, int>>> queue;
queue.push({root, {0, 0}});
while (!queue.empty()) {
auto [node, pos] = queue.front();
queue.pop();
int row = pos.first, col = pos.second;
colTable[col].emplace_back(row, node->val);
if (node->left) {
queue.push({node->left, {row + 1, col - 1}});
}
if (node->right) {
queue.push({node->right, {row + 1, col + 1}});
}
}
vector<vector<int>> result;
for (auto& [col, pairs] : colTable) {
sort(pairs.begin(), pairs.end());
vector<int> sortedCol;
for (auto& [row, val] : pairs) {
sortedCol.push_back(val);
}
result.push_back(sortedCol);
}
return result;
}
};Ставь 👍 и забирай 📚 Базу знаний